You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC222F] Expensive Expense

题目描述

有一棵 $N$ 个点的带边权的树，现在定义从点 $i$ 到点 $j$ 的距离是点 $i$ 走到点 $j$ 路上的边权和加上 $d _j$ ，问每个点到其它点的最长距离

输入格式

第一行一个整数 $N$ ，接下来 $N-1$ 行每行三个整数 $x,y,z$ 表示点 $x$ 和点 $y$ 之间有一条边权为 $z$ 的边，最后一行 $N$ 个整数表示 $d_i$ 。

$N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$ $D_1$ $D_2$ $\dots$ $D_N$

输出格式

$N$ 行，第 $i$ 行一个整数表示点 $i$ 到其他点的最远距离。

输入输出样例 #1

输入 #1

3
1 2 2
2 3 3
1 2 3

输出 #1

8
6
6

输入输出样例 #2

输入 #2

6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100

输出 #2

105
108
106
109
106
14

输入输出样例 #3

输入 #3

6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
1 2 3 4 5 6

输出 #3

5000000006
4000000006
3000000006
3000000001
4000000001
5000000001

说明/提示

数据范围

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i\ \leq\ N(1\ \leq\ i\ \leq\ N-1)$
• $1\ \leq\ B_i\ \leq\ N(1\ \leq\ i\ \leq\ N-1)$
• $1\ \leq\ C_i\ \leq\ 10^9(1\ \leq\ i\ \leq\ N-1)$
• $1\ \leq\ D_i\ \leq\ 10^9(1\ \leq\ i\ \leq\ N)$

样例解释 1

用 $d(i,j)$ 记录 $i$ 到 $j$ 的距离，则 $d(1,2)=2+2=4,d(1,3)=2+3+3=8,d(2,1)=2+1=3,d(2,3)=3+3=6,d(3,1)=3+2+1=6,d(3,2)=3+2=5$。