时空限制

1S/512M

题目描述

给定一棵由 $n$ 个节点和 $n-1$ 条无向边组成的树，第 $i$ 个节点的权值为 $a_i$。

定义一条路径的长度为路径上边的长度之和，定义节点 $i$ 和节点 $j$ 的距离 $\text{dis}(i,j)$ 为 $i$ 和 $j$ 之间最短路径的长度。

请你分别对 $p=1,2,\dots,n$，计算出 $\sum_{i=1}^na_i\times \text{dis}(p,i)$，即 $p$ 到每个节点的距离乘上该节点权值的和。

格式

输入格式

第一行包含一个整数 $n$，表示节点数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个节点的权值。

接下来 $n-1$ 行每行包含三个整数 $u_i,v_i,l_i$，表示节点 $u_i$ 和节点 $v_i$ 之间有一条长度为 $l_i$ 的无向边。数据保证这 $n-1$ 条边构成一棵 $n$ 个节点的树。

输出格式

输出 $n$ 行，每行一个整数，第 $i$ 个整数为 $p=i$ 时的答案。

样例

样例输入 #1

5
5 4 3 2 1
1 2 3
3 2 1
4 3 3
3 5 5

样例输出 #1

47
32
35
68
100

样例解释 #1

当 $p=1$ 时，每个节点和 $p$ 的距离分别是 $0,3,4,7,9$，答案为 $0\times5+3\times4+4\times3+7\times2+9\times1=47$。

当 $p=2$ 时，每个节点和 $p$ 的距离分别是 $3,0,1,4,6$，答案为 $3\times5+0\times4+1\times3+4\times2+6\times1=32$。

当 $p=3$ 时，每个节点和 $p$ 的距离分别是 $4,1,0,3,5$，答案为 $4\times5+1\times4+0\times3+3\times2+5\times1=35$。

当 $p=4$ 时，每个节点和 $p$ 的距离分别是 $7,4,3,0,8$，答案为 $7\times5+4\times4+3\times3+0\times2+8\times1=68$。

当 $p=5$ 时，每个节点和 $p$ 的距离分别是 $9,6,5,8,0$，答案为 $9\times5+6\times4+5\times3+8\times2+0\times1=100$。

数据规模

对于 $40\%$ 的数据， $n\leq 1000$。

另有 $20\%$ 的数据， $a_i=1$， $l_i=1$。

对于 $100\%$ 的数据， $1\leq n\leq 10^5$， $1\leq a_i\leq 10^4$， $1\leq u_i,v_i\leq n$， $1\leq l_i\leq 10^4$。