题目描述
有一颗 n 个点，n−1 条边带边权的树，现在定义从点 i 到点 j 的距离是点 i 走到点 j 路上的边权和加上 dj，问每个点到其它点的最长距离，要求 i=j。
输入格式
第一行输入一个整数 n
接下来 n−1 行每行三个整数代表 u,v,w
最后一行输入 n 个整数代表每个点的点权 di
输出格式
输出一共输出 n 行，每行一个整数代表离 i 最远的距离。
3
1 2 2
2 3 3
1 2 3
8
6
6
6
1 2 3
1 3 1
1 4 4
1 5 1
1 6 5
9 2 6 5 3 100
105
108
106
109
106
14
6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
1 2 3 4 5 6
5000000006
4000000006
3000000006
3000000001
4000000001
5000000001
提示
- 2 ≤ N ≤ 2 × 105
- 1 ≤ Ai ≤ N (1 ≤ i ≤ N−1)
- 1 ≤ Bi ≤ N (1 ≤ i ≤ N−1)
- 1 ≤ Ci ≤ 109 (1 ≤ i ≤ N−1)
- 1 ≤ Di ≤ 109 (1 ≤ i ≤ N)
