D. Alyona and a tree

Codeforces

IDCF740D

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdfs and similargraph matchingsgraphs

English · Original

Chinese · Translation

Formal · Original

Alyona has a tree with _n_ vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex _i_ she wrote _a__i_. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges). Let's define _dist_(_v_, _u_) as the sum of the integers written on the edges of the simple path from _v_ to _u_. The vertex _v_ controls the vertex _u_ (_v_ ≠ _u_) if and only if _u_ is in the subtree of _v_ and _dist_(_v_, _u_) ≤ _a__u_. Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex _v_ what is the number of vertices _u_ such that _v_ controls _u_. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 2·105). The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the integers written in the vertices. The next (_n_ - 1) lines contain two integers each. The _i_\-th of these lines contains integers _p__i_ and _w__i_ (1 ≤ _p__i_ ≤ _n_, 1 ≤ _w__i_ ≤ 109) — the parent of the (_i_ + 1)\-th vertex in the tree and the number written on the edge between _p__i_ and (_i_ + 1). It is guaranteed that the given graph is a tree. ## Output Print _n_ integers — the _i_\-th of these numbers should be equal to the number of vertices that the _i_\-th vertex controls. [samples] ## Note In the example test case the vertex 1 controls the vertex 3, the vertex 3 controls the vertex 5 (note that is doesn't mean the vertex 1 controls the vertex 5).

Alyona 有一棵包含 #cf_span[n] 个顶点的树。树的根是顶点 #cf_span[1]。在每个顶点中，Alyona 写了一个正整数，顶点 #cf_span[i] 中写的是 #cf_span[ai]。此外，女孩在树的每条边上也写了一个正整数（不同边上的整数可能不同）。定义 #cf_span[dist(v, u)] 为从顶点 #cf_span[v] 到顶点 #cf_span[u] 的简单路径上所有边上的整数之和。顶点 #cf_span[v] 控制顶点 #cf_span[u]（#cf_span[v ≠ u]）当且仅当 #cf_span[u] 在 #cf_span[v] 的子树中，且 #cf_span[dist(v, u) ≤ au]。 Alyona 想要定居在某个顶点。为此，她希望知道对于每个顶点 #cf_span[v]，有多少个顶点 #cf_span[u] 被 #cf_span[v] 控制。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——写在各个顶点中的整数。接下来的 #cf_span[(n - 1)] 行每行包含两个整数。第 #cf_span[i] 行包含整数 #cf_span[pi] 和 #cf_span[wi]（#cf_span[1 ≤ pi ≤ n]，#cf_span[1 ≤ wi ≤ 109]）——表示第 #cf_span[(i + 1)] 个顶点的父节点，以及连接 #cf_span[pi] 和 #cf_span[(i + 1)] 的边上的数值。保证给定的图是一棵树。请输出 #cf_span[n] 个整数——第 #cf_span[i] 个数应等于第 #cf_span[i] 个顶点所控制的顶点数量。在示例测试用例中，顶点 #cf_span[1] 控制顶点 #cf_span[3]，顶点 #cf_span[3] 控制顶点 #cf_span[5]（请注意，这并不意味着顶点 #cf_span[1] 控制顶点 #cf_span[5]）。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——写在各个顶点中的整数。接下来的 #cf_span[(n - 1)] 行每行包含两个整数。第 #cf_span[i] 行包含整数 #cf_span[pi] 和 #cf_span[wi]（#cf_span[1 ≤ pi ≤ n]，#cf_span[1 ≤ wi ≤ 109]）——表示第 #cf_span[(i + 1)] 个顶点的父节点，以及连接 #cf_span[pi] 和 #cf_span[(i + 1)] 的边上的数值。保证给定的图是一棵树。 ## Output 请输出 #cf_span[n] 个整数——第 #cf_span[i] 个数应等于第 #cf_span[i] 个顶点所控制的顶点数量。 [samples] ## Note 在示例测试用例中，顶点 #cf_span[1] 控制顶点 #cf_span[3]，顶点 #cf_span[3] 控制顶点 #cf_span[5]（请注意，这并不意味着顶点 #cf_span[1] 控制顶点 #cf_span[5]）。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of vertices. Let $ a_i \in \mathbb{Z}^+ $ be the value written at vertex $ i $, for $ i \in \{1, \dots, n\} $. Let $ T = (V, E) $ be a rooted tree with root $ 1 $, where $ V = \{1, \dots, n\} $. For each edge $ (p_i, i+1) $, let $ w_i \in \mathbb{Z}^+ $ be the weight of the edge connecting parent $ p_i $ to child $ i+1 $. Define $ \text{dist}(v, u) $ as the sum of edge weights along the unique simple path from $ v $ to $ u $. For vertex $ v $, let $ \text{subtree}(v) $ denote the set of vertices in the subtree rooted at $ v $, excluding $ v $ itself. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. $ 1 \leq w_i \leq 10^9 $ for all edges 4. The graph is a tree with root $ 1 $. **Objective** For each vertex $ v \in \{1, \dots, n\} $, compute: $$ c(v) = \left| \left\{ u \in \text{subtree}(v) \mid \text{dist}(v, u) \leq a_v \right\} \right| $$ Output $ c(1), c(2), \dots, c(n) $.

Samples

Input #1

Output #1

1 0 1 0 0

Input #2

Output #2

4 3 2 1 0

API Response (JSON)

{
  "problem": {
    "name": "D. Alyona and a tree",
    "description": {
      "content": "Alyona has a tree with _n_ vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex _i_ she wrote _a__i_. Moreover, the girl wrote a positive inte",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF740D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alyona has a tree with _n_ vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex _i_ she wrote _a__i_. Moreover, the girl wrote a positive inte...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alyona 有一棵包含 #cf_span[n] 个顶点的树。树的根是顶点 #cf_span[1]。在每个顶点中，Alyona 写了一个正整数，顶点 #cf_span[i] 中写的是 #cf_span[ai]。此外，女孩在树的每条边上也写了一个正整数（不同边上的整数可能不同）。\n\n定义 #cf_span[dist(v, u)] 为从顶点 #cf_span[v] 到顶点 #cf_span[u] 的简...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices.  \nLet $ a_i \\in \\mathbb{Z}^+ $ be the value written at vertex $ i $, for $ i \\in \\{1, \\dots, n\\} $.  \nLet $ T = (V, E) $ be a ro...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments