#4407. 寻宝 (trea)

寻宝 (trea)

[丛雨]捡到一张寻宝图,寻宝图是一棵由 NN 个节点组成的树,寻宝者到达每个点都会获得这个点上的宝藏,每个宝藏都有一定的价值,但是经过每条边也要支付一定的过路费。虽然每个点只有一个宝藏,但是过路费只要走过都要交。丛雨可不想盲目地去当冤大头,她想快速地计算出从每个点出发能获得的最大收益,请你帮她计算这个值。

输入格式(trea.in)

第一行为一个正整数 NN 。接下来 N1N-1 行,每行三个整数,描述一条双向边的两个端点 x,yx, y 和过路费 zz 。 最后一行 NN 个数,表示每个点上宝藏的价值 aia_i

输出格式(trea.out)

输出 NN 行,每行一个数。第 ii 行表示从 ii 出发的最大收益。

输入样例

6 
1 2 1 
2 3 3 
3 4 36 
3 6 13 
3 5 2 
6 8 9 10 13 1

输出样例

30 
29 
28 
10 
30 
16

数据范围

对于 20%20\% 的数据,满足 N10N \le 10 。 对于 50%50\% 的数据,满足 N1000N \le 1000 。 对于 100%100\% 的数据,满足 1N3105,1z,ai1051 \le N \le 3*10^5, 1 \le z, a_i \le 10^5