题目描述

给定一棵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

提示

给定一棵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统计出每一次行走时经过的所有点的权值和。