[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步就能到达y,那么他会一步走到y。请帮助Byteasar统计出每一次行走时经过的所有点的权值和。

输入输出格式

输入格式


第一行包含一个正整数n(2<=n<=50000)。表示节点的个数。第二行包含n个正整数,其中第i个数为a[i](1<=a[i]<=10000),分别表示每个点的权值。接下来n-1行,每行包含两个正整数u,v(1<=u,v<=n),表示u与v之间有一条边。接下来一行包含n个互不相同的正整数,其中第i个数为b[i](1<=b[i]<=n),表示行走路线。接下来一行包含n-1个正整数,其中第i个数为c[i](1<=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

说明

给定一棵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步就能到达y,那么他会一步走到y。 请帮助Byteasar统计出每一次行走时经过的所有点的权值和。