레이팅 미적용Toni decided to create a task for HONI (and COCI). Since he doesn’t like kids, he decided to make the
task as difficult as possible. He came up with a complex problem involving a tree that constantly changes,
solely to make contestants suffer as much as possible.
You are given a weightless tree with \(N\) nodes, where the root of the tree is node 1. Each node has an
associated value \(v\)[\(i\)]. The structure of the tree is defined using an array \(p\)[\(i\)], where for each \(i\) from 1 to
\(N - 1\), \(p\)[\(i\)] denotes the parent of \(i + 1\).
A function \(f\)(\(y\)) is defined for a node \(y\) in the tree as:
\(f\)(\(y\)) =
X
\(x\)∈\(S_{y}\)
\(d\)(x, y) · \(v\)[\(x\)]
where \(d\)(x, y) denotes the distance between nodes \(x\) and \(y\), while \(S_{y}\) contains all nodes for which \(y\) is an
ancestor.
You are given \(Q\) queries with two nodes \(x\) and \(y\). For each query, the following transformation must be
simulated in the tree, and the function \(f\)(\(y\)) needs to be calculated:
1. Attach all nodes for which \(x\) is the parent to the parent of \(x\)
2. Remove \(x\) from the tree
3. Insert node \(x\) back into the tree, between \(y\) and the descendant of \(y\) from whose subtree \(x\) was
removed.
If \(y\) is the parent of \(x\), the tree remains unchanged. It is always true that \(x\) is in the subtree of \(y\). For
each query, the value of \(f\)(\(y\)) must be calculated after the tree is temporarily modified according to the
procedure described above. The tree modifications are not permanent, i.e. after each query, the tree
returns to its original state.
Subtask 1 (21 points): \(1 \le N\), \(Q \le 1000\)
Subtask 2 (37 points): Tree is a chain, \(p\)[\(i\)] = \(i\) for every \(i\) from 1 to \(N - 1\)
Subtask 3 (22 points): Each node will be the parent of at most 20 nodes
Subtask 4 (40 points): No additional constraints.
The first line contains two integers \(N\) and \(Q\) (\(1 \le N\), \(Q \le 5 \cdot 10^{5}\)), the number of nodes in the tree and
the number of queries, respectively.
The second line contains \(N\) integers \(v\)[\(i\)] (\(1 \le v\)[\(i\)] ≤\(10^{6}\)), representing the value of each node.
The third line contains \(N - 1\) integers \(p\)[\(i\)] (\(1 \le p\)[\(i\)] ≤\(i\)), where \(p\)[\(i\)] denotes the parent of node \(i + 1\).
Each of the next \(Q\) lines contains two integers \(x\) and \(y\) (\(1 \le x\), \(y \le N\)), denoting the nodes involved in the
operation described above.
In the next \(Q\) lines output the value of the function \(f\)(\(y\)) on the modified tree.
3 1
1 2 3
1 2
3 173 2
4 5 6
1 1
2 1
3 111
115 3
2 5 2 2 2
1 2 3 2
4 3
3 2
5 12
8
26Clarification of the first example: After applying the operation on a tree, node 3 is at a distance of 1
from node 1, and node 2 is at a distance of 2 from node 1. The result is 3 + 2 · 2 = 7.