P8990 [Peking University Training 2021] Xiaoming’s Tree

CTT2021 D3T1

Xiaoming has a tree with $n$ nodes rooted at $1$. Each non-root node has a lamp on it. He is given a permutation $a_1, a_2, \dots, a_{n-1}$ of $2 \thicksim n$. He also has a counter, initially $0$. He will turn on these $n-1$ lamps one by one in the order of the permutation. After each lamp operation, he will check whether the whole tree is beautiful. If it is beautiful, the counter will be increased by the number of connected components formed by the nodes whose lamps are currently on. After the $n-1$ lamp operations, the value of the counter is called the answer of this tree. A tree is beautiful if and only if, for every node whose lamp is on, all nodes in the subtree of this node are also on. Xiaoming thinks this problem is too easy, so he wants to make the tree move. After the initial query, he will delete one edge in the tree and add one edge, ensuring that the graph is still a tree after the modification. He wants to know, after each modification, if he resets the counter to zero and turns on the lamps again and counts again, what the answer of the tree is.

The first line contains two integers $n, m$, meaning the tree has $n$ nodes and there are $m$ modifications. The next $n-1$ lines each contain $2$ integers, describing an edge. The next line contains $n-1$ integers $a_i$, representing a permutation of $2 \thicksim n$. The next $m$ lines each contain four integers $x_1, y_1, x_2, y_2$, meaning to remove the edge between $x_1, y_1$ and add an edge between $x_2, y_2$. The testdata is guaranteed to be valid.

Output $m+1$ lines in total. The first line is the answer for the initial tree. The next $m$ lines are the answers after each modification.

- Subtask $1$ ($10$ points): it is guaranteed that $2 \leq n \leq 500000$, $m = 0$. - Subtask $2$ ($20$ points): it is guaranteed that $2 \leq n \leq 8000$, $0 \leq m \leq 8000$. - Subtask $3$ ($70$ points): it is guaranteed that $2 \leq n \leq 500000$, $0 \leq m \leq 500000$. Translated by ChatGPT 5