Alyona and a tree

题意翻译

## 题目描述： Alyona有一棵有 $n$ 个节点的树。这棵树的根节点是 $1$。在每个节点里，Alyona写了一个正整数，在节点 $i$ 她写了正整数 $a_i$ 。另外，她在这棵树上的每条边上写了一个正整数（不同边上可能有不同的数）。 让我们定义 $dist(v,u)$ 作为从 $v$ 到 $u$ 的简单路径上的边权和。 当且仅当 $u$ 在 $v$ 的子树中并且 $dist(v,u)\leq a_u$，顶点 $v$ 控制顶点 $u(v!=u)$ 。 Alyona想在某些顶点定居。为了做到这件事，她想知道在每个节点 $v$ 能控制几个节点。 ## 输入格式： 第一行包含一个整数 $n (1\leq n\leq 2\times 10^5)$ 第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n(1\leq a_i\leq 10^9)$ ,作为节点 $i$ 的数。 下面的 $n-1$ 行，每行有两个整数。第 $i$ 行包含整数 $p_i,w_i(1\leq p_i\leq n,1\leq w_i\leq 10^9)$ ,分别为节点 $i+1$ 的在树上的父节点和 $p_i$ 和 $(i+1)$ 的边上的数字。 数据保证是个树。 ## 输出格式： 输出 $n$ 个整数，第 $i$ 个数为节点 $i$ 能控制的点数。 ## 样例说明： 在样例中，节点 $1$ 控制了节点 $3$ ，节点 $3$ 控制节点 $5$ （注意，这并不代表节点 $1$ 控制了节点 $5$ ） Translated by @lolte

题目描述

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 $ .

输入输出格式

输入格式

The first line contains single integer $ n $ ( $ 1<=n<=2·10^{5} $ ). The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ) — 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}<=10^{9} $ ) — 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.

输出格式

Print $ n $ integers — the $ i $ -th of these numbers should be equal to the number of vertices that the $ i $ -th vertex controls.

输入输出样例

输入样例 #1

5
2 5 1 4 6
1 7
1 1
3 5
3 6

输出样例 #1

1 0 1 0 0

输入样例 #2

5
9 7 8 6 5
1 1
2 1
3 1
4 1

输出样例 #2

4 3 2 1 0

说明

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有一棵有 $n$ 个节点的树。这棵树的根节点是 $1$。在每个节点里，Alyona写了一个正整数，在节点 $i$ 她写了正整数 $a_i$ 。另外，她在这棵树上的每条边上写了一个正整数（不同边上可能有不同的数）。 让我们定义 $dist(v,u)$ 作为从 $v$ 到 $u$ 的简单路径上的边权和。 当且仅当 $u$ 在 $v$ 的子树中并且 $dist(v,u)\leq a_u$，顶点 $v$ 控制顶点 $u(v!=u)$ 。 Alyona想在某些顶点定居。为了做到这件事，她想知道在每个节点 $v$ 能控制几个节点。 ## 输入格式： 第一行包含一个整数 $n (1\leq n\leq 2\times 10^5)$ 第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n(1\leq a_i\leq 10^9)$ ,作为节点 $i$ 的数。 下面的 $n-1$ 行，每行有两个整数。第 $i$ 行包含整数 $p_i,w_i(1\leq p_i\leq n,1\leq w_i\leq 10^9)$ ,分别为节点 $i+1$ 的在树上的父节点和 $p_i$ 和 $(i+1)$ 的边上的数字。 数据保证是个树。 ## 输出格式： 输出 $n$ 个整数，第 $i$ 个数为节点 $i$ 能控制的点数。 ## 样例说明： 在样例中，节点 $1$ 控制了节点 $3$ ，节点 $3$ 控制节点 $5$ （注意，这并不代表节点 $1$ 控制了节点 $5$ ） Translated by @lolte