g6-07513. 带权距离和 未做

给定一棵 $n$ 个结点的树，每条边有正整数长度。对每个结点 $u$，求所有结点到 $u$ 的带权距离之和（两点间的带权距离 = 路径上各边长度之和）。

第一行一个整数 $n$。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示一条长度为 $w$ 的边。

一行 $n$ 个整数，第 $i$ 个数表示所有结点到结点 $i$ 的带权距离之和。

输入：

3
1 2 2
2 3 3

输出：

7 5 8

链上边长为 $2,3$：到 $1$ 的带权距离和为 $0+2+5=7$；到 $2$ 的为 $2+0+3=5$；到 $3$ 的为 $5+3+0=8$。

• 对于 $30\%$ 的测试点，$1\le n\le 100$；
• 对于 $60\%$ 的测试点，$1\le n\le 5000$；
• 对于全部测试点，$1\le n\le 2\times 10^5$，$1\le w\le 10^6$；满档包含链形数据。