Traverse Tree with Variable Step Sizes

Given a tree with $n$ nodes where each edge has a length of $1$ and node $i$ has weight $a_i$, Byteasar wants to traverse the tree in a specific order. He is given a permutation $b = [b_1, b_2, \dots, b_n]$ of the nodes. For each $1 \le i \le n-1$, he travels from node $b_i$ to node $b_{i+1}$ along the unique simple path in the tree. The $i$-th journey is taken with a step size of $c_i$, meaning that starting from node $b_i$, he repeatedly moves $k=c_i$ edges forward along the path until he reaches $b_{i+1}$. It is guaranteed that the total number of edges on the path is a multiple of $c_i$. For each journey, output the sum of the weights of all the nodes visited (including both the starting and ending nodes).

inputFormat

The input begins with a line containing a single integer $n$ ($n \ge 1$) representing the number of nodes in the tree.

The next line contains $n$ integers $a_1,a_2,\dots,a_n$, where $a_i$ is the weight of node $i$.

Each of the following $n-1$ lines contains two integers $u$ and $v$, indicating an undirected edge between nodes $u$ and $v$.

The next line contains $n$ integers representing a permutation $b_1,b_2,\dots,b_n$ of the nodes.

The last line contains $n-1$ integers $c_1,c_2,\dots,c_{n-1}$, where $c_i$ is the step size for the journey from $b_i$ to $b_{i+1}$.

outputFormat

Output $n-1$ lines. The $i$-th line should contain a single integer: the sum of the weights of the nodes visited during the journey from $b_i$ to $b_{i+1}$ when taking steps of length $c_i$ along the unique path.

sample

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

4
5
11
12