Public Judge

pjudge

Time Limit: 4 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21728. 【CTS Round #1 Day 1】地雷

统计

给定一棵 $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$