昂贵的旅途 - 代码源竞赛平台

题目描述

蜗蜗准备在一张树形地图上旅行。地图中有 $N$ 个地点，编号为 $1$ 到 $N$ ，地点之间由 $N-1$ 条双向道路连接。经过每条道路都需要支付对应的通行费，在地点 $j$ 结束旅行还需要支付终点费用 $D_j$ 。

从地点 $i$ 前往地点 $j$ 时，蜗蜗沿两点之间的唯一简单路径行走。总费用等于这条路径上的通行费之和，再加上 $D_j$ ，不计算其他地点的终点费用。

对于每个出发地点 $i$ ，蜗蜗必须选择一个与它不同的地点作为终点。请你分别求出各个出发地点对应的最大旅行费用。

第一行包含一个整数 $N$ ，表示地点数量。

接下来 $N-1$ 行，每行包含三个整数 $A_i,B_i,C_i$ ，表示地点 $A_i$ 与地点 $B_i$ 之间有一条双向道路，经过这条道路需要支付 $C_i$ 的通行费。

最后一行包含 $N$ 个整数 $D_1,D_2,\ldots,D_N$ ，表示在每个地点结束旅行时需要支付的终点费用。

输出 $N$ 行，每行一个整数。第 $i$ 行表示从地点 $i$ 出发、前往其他地点时能够产生的最大旅行费用。

2
1 2 3
100 1

4
103

从地点 $1$ 出发，只能选择地点 $2$ 作为终点，总费用为 $3+1=4$ 。

从地点 $2$ 出发，只能选择地点 $1$ 作为终点，总费用为 $3+100=103$ 。

对于 100% 的数据，保证 $2\le N\le 2\times 10^5$ ， $1\le A_i,B_i\le N$ ， $1\le C_i\le 10^9$ ， $1\le D_i\le 10^9$ 。

输入的道路构成一棵树。