{"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 integer to every edge of the tree (possibly, different integers on different edges).\n\nLet's define _dist_(_v_, _u_) as the sum of the integers written on the edges of the simple path from _v_ to _u_.\n\nThe 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_.\n\nAlyona 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_.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 2·105).\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the integers written in the vertices.\n\nThe 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).\n\nIt is guaranteed that the given graph is a tree.\n\n## Output\n\nPrint _n_ integers — the _i_\\-th of these numbers should be equal to the number of vertices that the _i_\\-th vertex controls.\n\n[samples]\n\n## Note\n\nIn 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).","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] 的简单路径上所有边上的整数之和。\n\n顶点 #cf_span[v] 控制顶点 #cf_span[u]（#cf_span[v ≠ u]）当且仅当 #cf_span[u] 在 #cf_span[v] 的子树中，且 #cf_span[dist(v, u) ≤ au]。\n\nAlyona 想要定居在某个顶点。为此，她希望知道对于每个顶点 #cf_span[v]，有多少个顶点 #cf_span[u] 被 #cf_span[v] 控制。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）——写在各个顶点中的整数。\n\n接下来的 #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)] 的边上的数值。\n\n保证给定的图是一棵树。\n\n请输出 #cf_span[n] 个整数——第 #cf_span[i] 个数应等于第 #cf_span[i] 个顶点所控制的顶点数量。\n\n在示例测试用例中，顶点 #cf_span[1] 控制顶点 #cf_span[3]，顶点 #cf_span[3] 控制顶点 #cf_span[5]（请注意，这并不意味着顶点 #cf_span[1] 控制顶点 #cf_span[5]）。\n\n## Input\n\n第一行包含一个整数 #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)] 的边上的数值。保证给定的图是一棵树。\n\n## Output\n\n请输出 #cf_span[n] 个整数——第 #cf_span[i] 个数应等于第 #cf_span[i] 个顶点所控制的顶点数量。\n\n[samples]\n\n## Note\n\n在示例测试用例中，顶点 #cf_span[1] 控制顶点 #cf_span[3]，顶点 #cf_span[3] 控制顶点 #cf_span[5]（请注意，这并不意味着顶点 #cf_span[1] 控制顶点 #cf_span[5]）。","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 rooted tree with root $ 1 $, where $ V = \\{1, \\dots, n\\} $.  \nFor 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 $.  \n\nDefine $ \\text{dist}(v, u) $ as the sum of edge weights along the unique simple path from $ v $ to $ u $.  \nFor vertex $ v $, let $ \\text{subtree}(v) $ denote the set of vertices in the subtree rooted at $ v $, excluding $ v $ itself.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq w_i \\leq 10^9 $ for all edges  \n4. The graph is a tree with root $ 1 $.  \n\n**Objective**  \nFor each vertex $ v \\in \\{1, \\dots, n\\} $, compute:  \n$$\nc(v) = \\left| \\left\\{ u \\in \\text{subtree}(v) \\mid \\text{dist}(v, u) \\leq a_v \\right\\} \\right|\n$$  \nOutput $ c(1), c(2), \\dots, c(n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF740D","tags":["binary search","data structures","dfs and similar","graph matchings","graphs"],"sample_group":[["5\n2 5 1 4 6\n1 7\n1 1\n3 5\n3 6","1 0 1 0 0"],["5\n9 7 8 6 5\n1 1\n2 1\n3 1\n4 1","4 3 2 1 0"]],"created_at":"2026-03-03 11:00:39"}}