[POI2015]Odwiedziny

时间限制:20s      空间限制:128MB

题目描述

给定一棵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行,每行一个正整数,依次输出每次行走时经过的所有点的权值和


样例输入

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

样例输出

10
6
10
5

提示

鸣谢Claris


题目来源

鸣谢Claris