给定一棵 $n$ 个顶点的树,其中第 $i$($1 \le i \le n-1$)条边连接了顶点 $u_i$ 与 $v_i$($1 \le u_i, v_i \le n$),其长度为 $w_i$。
在每个顶点上均埋藏着一棵地雷。第 $i$($1 \le i \le n$)个顶点上的地雷的爆炸半径为 $R_i$ ,伤害值为 $h_i$ 。
我们定义 $\mathrm{dist}(i, j)$ 表示在树上顶点 $i$ 与顶点 $j$ 的最短距离。即,$\mathrm{dist}(i, j)$ 为顶点 $i$ 与 $j$ 之间唯一的简单路径的边权之和。
当顶点 $i$ 处的地雷爆炸时,所有距离其不超过 $R_i$ 的地雷都会一起爆炸。即,对于所有满足 $\mathrm{dist}(i, j) \le R_i$ 的地雷 $j$,如果其还没有爆炸,那么他也会被引爆。
对于每个 $i$($i = 1, 2, \cdots, n$),你希望求出,如果在起始时引爆了顶点 $i$ 处的地雷,则最终所有被引爆的地雷的伤害值之和。
输入格式
输入的第一行包含一个整数 $n$。
接下来一行,包含 $n$ 个整数 $h_1, h_2, \cdots, h_n$,描述每个顶点上地雷的伤害值。
接下来一行,包含 $n$ 个整数 $R_1, R_2, \cdots, R_n$,描述每个顶点上地雷的半径。
接下来 $n-1$ 行,每行三个整数 $u_i, v_i, w_i$,描述一条边。
输出格式
输出一行,包含 $n$ 个整数。其中第 $i$($i = 1, 2, \cdots, n$)个整数描述了如果在起始时引爆了顶点 $i$ 处的地雷,则最终所有被引爆的地雷的伤害值之和。
样例数据
样例 1 输入
5
1 10 100 1000 10000
3 2 3 1 3
1 2 3
1 3 1
2 4 3
2 5 2
样例 1 输出
10111 10010 10111 1000 10010
样例 2 输入
9
3 1 4 1 5 9 2 6 5
9 9 8 2 4 4 3 5 3
1 2 9
1 3 10
1 4 5
2 5 7
2 6 8
5 7 6
7 8 3
6 9 10
样例 2 输出
19 19 4 1 5 9 8 8 5
子任务
对于所有数据,$1 \le n \le 10^5$,$1\le h_i\le 10^9$,$0 \le R_i \le 10^{18}$,$1 \le u_i, v_i \le n$,$1 \le w_i \le 10^{12}$。
子任务编号 | $n \le$ | 特殊性质 | 分值 |
---|---|---|---|
$1$ | $100$ | 无 | $5$ |
$2$ | $5 \times 10^3$ | $9$ | |
$3$ | $6 \times 10^4$ | $12$ | |
$4$ | $h_i=1$ | $19$ | |
$5$ | $8 \times 10^4$ | 无 | $21$ |
$6$ | $10^5$ | $u_i = i, v_i = i+1$ | $11$ |
$7$ | 无 | $23$ |