P3591 [POI 2015 R3] Visits

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.

- 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 $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.

Original title: Odwiedziny. Translated by ChatGPT 5