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[u]。
第一行包含一个整数 #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[pi] 到 #cf_span[(i + 1)] 上写的数为 #cf_span[wi]。
保证给出的图是一棵树。
请输出 #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[pi] 到 #cf_span[(i + 1)] 上写的数为 #cf_span[wi]。保证给出的图是一棵树。
## 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}^+ $ denote the weight of the edge connecting parent $ p_i $ to child $ i+1 $, for $ i \in \{1, \dots, n-1\} $.
Define $ \text{dist}(v, u) $ as the sum of edge weights along the unique simple path from $ v $ to $ u $.
Define $ \text{subtree}(v) $ as the set of all 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 $ i \in \{1, \dots, n-1\} $
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) $.
API Response (JSON)
{
"problem": {
"name": "B. 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": "CF739B"
},
"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"
}
]
}