[POI2015] ODW

题目描述

给定一棵 $n$ 个点的树,树上每条边的长度都为 $1$,第 $i$ 个点的权值为 $a_i$。 Byteasar 想要走遍这整棵树,他会按照某个 $1$ 到 $n$ 的全排列 $b$ 走 $n-1$ 次,第 $i$ 次他会从 $b_i$ 点走到 $b_{i + 1}$ 点,并且这一次的步伐大小为 $c_i$。 对于一次行走,假设起点为 $x$,终点为 $y$,步伐为 $k$,那么Byteasar会从 $x$ 开始,每步往前走 $k$ 条边,数据保证了每次行走的距离是 $k$ 的倍数。 请帮助 Byteasar 统计出每一次行走时经过的所有点的权值和。

输入输出格式

输入格式


第一行包含一个正整数 $n$($2 \le n \le 50000$)。表示节点的个数。 第二行包含 $n$ 个正整数,其中第 $i$ 个数为 $a_i$($1 \le a_i \le 10000$),分别表示每个点的权值。 接下来 $n-1$ 行,每行包含两个正整数 $u,v$($1 \le u,v \le n$),表示 $u$ 与 $v$ 之间有一条边。 接下来一行包含 $n$ 个互不相同的正整数,其中第 $i$ 个数为 $b_i$($1 \le b_i \le n$),表示行走路线。 接下来一行包含 $n-1$ 个正整数,其中第 $i$ 个数为 $c_i$($1 \le c_i < n$),表示每次行走的步伐大小。

输出格式


包含 $n-1$ 行,每行一个正整数,依次输出每次行走时经过的所有点的权值和。

输入输出样例

输入样例 #1

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

输出样例 #1

10
6
10
5

说明

原题名称:Odwiedziny。