Description

You are given a tree with $n$ vertices. Each edge has length $1$, and the weight of vertex $i$ is $a_i$.

Byteasar wants to traverse the whole tree. He will follow a permutation $b$ of $1$ to $n$ and make $n-1$ walks. On the $i$-th walk, he goes from vertex $b_i$ to vertex $b_{i+1}$, and the step size for this walk is $c_i$.

For a single walk, suppose the start is $x$, the end is $y$, and the step size is $k$. Byteasar starts at $x$ and moves forward along the unique path from $x$ to $y$, taking steps of exactly $k$ edges each time. The testdata guarantees that the distance of each walk is a multiple of $k$.

Please help Byteasar compute, for each walk, the sum of the weights of all vertices he visits during that walk.

Input Format

• The first line contains a positive integer $n$ ($2 \le n \le 50000$), the number of vertices.
• The second line contains $n$ positive integers, where the $i$-th number is $a_i$ ($1 \le a_i \le 10000$), the weight of vertex $i$.
• The next $n-1$ lines each contain two positive integers $u, v$ ($1 \le u, v \le n$), indicating that there is an edge between $u$ and $v$.
• The next line contains $n$ distinct positive integers, where the $i$-th number is $b_i$ ($1 \le b_i \le n$), describing the route (a permutation).
• The next line contains $n-1$ positive integers, where the $i$-th number is $c_i$ ($1 \le c_i < n$), the step size for the $i$-th walk.

Output Format

Output $n-1$ lines. The $i$-th line should contain one positive integer: the sum of the weights of all vertices visited during the $i$-th walk.

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

Hint

Original title: Odwiedziny.

Translated by ChatGPT 5