시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 125 | 30 | 20 | 17.544% |
Bobo has a rooted tree with $n$ nodes which are conveniently labeled with $1, 2, \dots, n$. Node $1$ is the root, and the $i$-th node has weight $w_i$.
He would like to find out $f(2), f(3), \dots, f(n)$ where
$$f(i) = \sum_{j = 1}^{i - 1} w_{\mathrm{LCA}(i, j)}\text{.}$$
The input contains zero or more test cases, and is terminated by end-of-file. For each test case:
The first line contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$).
The second line contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \leq w_i \leq 10^4$).
The third line contains $(n - 1)$ integers $p_2, p_3, \dots, p_n$, where $p_i$ denotes an edge from the $p_i$-th node to the $i$-th node ($1 \leq p_i \leq n$). The edges form a tree.
It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$.
For each test case, output $(n - 1)$ integers: $f(2), f(3), \dots, f(n)$.
3 1 2 3 1 1 5 1 2 3 4 5 1 2 2 1
1 2 1 3 5 4