题目描述

给定一棵 $N$ 个节点的树，节点从 $1$ 到 $N$ 编号。每个节点 $i$ 都有一个非负整数权值 $W_i$。

我们定义 $\text{Dist}(u, v)$ 为节点 $u$ 和 $v$ 之间在树上的最短路径上的边数。

对于树上的每一个节点 $i$，你需要计算一个值 $S_i$，它表示树上所有到节点 $i$ 的距离不超过 $3$ 的节点的权值之和。

即，你需要计算：

$$S_i = \sum_{j=1}^{N} W_j \cdot [\text{Dist}(i, j) \le 3] $$

其中 $[P]$ 是 Iverson 括号，当条件 $P$ 成立时为 $1$，否则为 $0$。

请输出所有节点 $S_i$ 的值。

输入格式

第一行包含一个正整数 $N$，表示树的节点数。

第二行包含 $N$ 个非负整数，其中第 $i$ 个数表示节点 $i$ 的权值 $W_i$。

接下来 $N-1$ 行，每行包含两个正整数 $u, v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出格式

输出一行 $N$ 个非负整数，其中第 $i$ 个数表示节点 $i$ 的答案 $S_i$。相邻的数字之间用空格隔开。

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

10 15 15 15 14

样例解释:

树的结构是 $1-2-3-4-5$，节点权值分别为 $1, 2, 3, 4, 5$.

• $S_1$: 到 $1$ 距离 $\le 3$ 的节点有 $\{1, 2, 3, 4\}$。 $S_1 = W_1+W_2+W_3+W_4 = 1+2+3+4 = 10$。
• $S_2$: 到 $2$ 距离 $\le 3$ 的节点有 $\{1, 2, 3, 4, 5\}$。 $S_2 = 1+2+3+4+5 = 15$。
• $S_3$: 到 $3$ 距离 $\le 3$ 的节点有 $\{1, 2, 3, 4, 5\}$。 $S_3 = 1+2+3+4+5 = 15$。
• $S_4$: 到 $4$ 距离 $\le 3$ 的节点有 $\{1, 2, 3, 4, 5\}$。 $S_4 = 1+2+3+4+5 = 15$。
• $S_5$: 到 $5$ 距离 $\le 3$ 的节点有 $\{2, 3, 4, 5\}$。 $S_5 = W_2+W_3+W_4+W_5 = 2+3+4+5 = 14$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le W_i \le 10^9$。

• 子任务 1（30 分）：$1 \le N \le 100$。
• 子任务 2（30 分）：$1 \le N \le 1000$。
• 子任务 3（40 分）：$1 \le N \le 10^5$。