D. Broken BST

Codeforces

IDCF797D

Time1000ms

Memory256MB

Difficulty—

data structuresdfs and similar

English · Original

Chinese · Translation

Formal · Original

Let _T_ be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tree. Every vertex has an integer number written on it. Following algorithm is run on every value from the tree _T_: 1. Set pointer to the root of a tree. 2. Return success if the value in the current vertex is equal to the number you are looking for 3. Go to the left child of the vertex if the value in the current vertex is greater than the number you are looking for 4. Go to the right child of the vertex if the value in the current vertex is less than the number you are looking for 5. Return fail if you try to go to the vertex that doesn't exist Here is the pseudo-code of the described algorithm: bool find(TreeNode t, int x) { if (t == null) return false; if (t.value == x) return true; if (x < t.value) return find(t.left, x); else return find(t.right, x); } find(root, x); The described algorithm works correctly if the tree is binary search tree (i.e. for each node the values of left subtree are less than the value in the node, the values of right subtree are greater than the value in the node). But it can return invalid result if tree is not a binary search tree. Since the given tree is not necessarily a binary search tree, not all numbers can be found this way. Your task is to calculate, how many times the search will fail being running on every value from the tree. If the tree has multiple vertices with the same values on them then you should run algorithm on every one of them separately. ## Input First line contains integer number _n_ (1 ≤ _n_ ≤ 105) — number of vertices in the tree. Each of the next _n_ lines contains 3 numbers _v_, _l_, _r_ (0 ≤ _v_ ≤ 109) — value on current vertex, index of the left child of the vertex and index of the right child of the vertex, respectively. If some child doesn't exist then number - 1 is set instead. Note that different vertices of the tree may contain the same values. ## Output Print number of times when search algorithm will fail. [samples] ## Note In the example the root of the tree in vertex 2. Search of numbers 5 and 15 will return fail because on the first step algorithm will choose the subtree which doesn't contain numbers you are looking for.

设 #cf_span[T] 为任意二叉树——每个顶点最多有两个子节点的树。给定的树是有根的，因此存在唯一一个没有父节点的顶点——即树的根。每个顶点上写有一个整数。对树 #cf_span[T] 中的每个值运行以下算法：以下是所描述算法的伪代码：如果该树是二叉搜索树（即对每个节点，其左子树中的值均小于该节点的值，右子树中的值均大于该节点的值），则上述算法能正确运行。但如果树不是二叉搜索树，则可能返回错误结果。由于给定的树不一定是二叉搜索树，因此并非所有数值都能通过此方式找到。你的任务是计算：当对树中的每个值运行该搜索算法时，算法失败的次数。如果树中存在多个具有相同值的顶点，则应对每个值分别运行算法。第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——树中顶点的数量。接下来的 #cf_span[n] 行每行包含 #cf_span[3] 个整数 #cf_span[v], #cf_span[l], #cf_span[r]（#cf_span[0 ≤ v ≤ 10^9]）——当前顶点的值、左子节点的索引和右子节点的索引。如果某个子节点不存在，则用 #cf_span[ - 1] 表示。注意，树中不同顶点可能包含相同的值。请输出搜索算法失败的次数。在示例中，树的根位于顶点 #cf_span[2]。搜索数值 #cf_span[5] 和 #cf_span[15] 会失败，因为在第一步中算法会选择不包含目标值的子树。 ## Input 第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10^5]）——树中顶点的数量。接下来的 #cf_span[n] 行每行包含 #cf_span[3] 个整数 #cf_span[v], #cf_span[l], #cf_span[r]（#cf_span[0 ≤ v ≤ 10^9]）——当前顶点的值、左子节点的索引和右子节点的索引。如果某个子节点不存在，则用 #cf_span[ - 1] 表示。注意，树中不同顶点可能包含相同的值。 ## Output 请输出搜索算法失败的次数。 [samples] ## Note 在示例中，树的根位于顶点 #cf_span[2]。搜索数值 #cf_span[5] 和 #cf_span[15] 会失败，因为在第一步中算法会选择不包含目标值的子树。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of vertices in a rooted binary tree. For each vertex $ i \in \{1, \dots, n\} $, let: - $ v_i \in \mathbb{Z} $ be the value stored at vertex $ i $, - $ l_i \in \{ -1 \} \cup \{1, \dots, n\} $ be the index of the left child ($ -1 $ if absent), - $ r_i \in \{ -1 \} \cup \{1, \dots, n\} $ be the index of the right child ($ -1 $ if absent). Let $ T = (V, E) $ be the tree with root at vertex $ r $ (the unique vertex with no parent). Let $ \text{Search}(x) $ be the standard BST search algorithm: - Start at the root. - At each node $ i $: - If $ x = v_i $, return success. - Else if $ x < v_i $, recurse on left child if exists; else fail. - Else if $ x > v_i $, recurse on right child if exists; else fail. - If no node is reached, return fail. **Constraints** 1. $ 1 \le n \le 10^5 $ 2. $ 0 \le v_i \le 10^9 $ 3. $ l_i, r_i \in \{-1\} \cup \{1, \dots, n\} $, with exactly one root (no parent). **Objective** Count the number of vertices $ i \in \{1, \dots, n\} $ for which $ \text{Search}(v_i) $ fails, i.e., the algorithm does not reach vertex $ i $ when searching for $ v_i $, despite $ v_i $ being present in the tree.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Broken BST",
    "description": {
      "content": "Let _T_ be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tre",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF797D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let _T_ be arbitrary binary tree — tree, every vertex of which has no more than two children. Given tree is rooted, so there exists only one vertex which doesn't have a parent — it's the root of a tre...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "设 #cf_span[T] 为任意二叉树——每个顶点最多有两个子节点的树。给定的树是有根的，因此存在唯一一个没有父节点的顶点——即树的根。每个顶点上写有一个整数。对树 #cf_span[T] 中的每个值运行以下算法：\n\n以下是所描述算法的伪代码：\n\n如果该树是二叉搜索树（即对每个节点，其左子树中的值均小于该节点的值，右子树中的值均大于该节点的值），则上述算法能正确运行。但如果树不是二叉搜索树，则可...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices in a rooted binary tree.  \nFor each vertex $ i \\in \\{1, \\dots, n\\} $, let:  \n- $ v_i \\in \\mathbb{Z} $ be the value stored at vertex...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments