4381 - [POI2015]Odwiedziny

给定一棵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个数为ai，分别表示每个点的权值。 接下来n-1行，每行包含两个正整数u,v(1<=u,v<=n)，表示u与v之间有一条边。 接下来一行包含n个互不相同的正整数，其中第i个数为bi，表示行走路线。 接下来一行包含n-1个正整数，其中第i个数为ci，表示每次行走的步伐大小。

输出

包含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

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题