No Abstracts.

I can still not type Chinese now. sad.

# Des.

Giving you a tree and $Q$ operations, they might be change the root of the tree or query the number of pairs with the same value in two subtrees.

# Sol.

Tree Tech: We’ve known that changing the root of a tree doesn’t destroy the structure of the tree, and a subtree will be divided into at most 2 parts, so the questions are still for intervals.

But how to deal the questions on intervals? It have a prerequisite problem BZOJ 5016, according from it we can convert interval problem to a prefix problem, as: $P(r_1, r_2) - P(l_1 - 1, r_2) - P(r_1, l_2 - 1) + P(l_1 - 1, l_2 - 1)$, where P is the answer of 2 prefixes. And a prefix problem can be update in $O(1)$ time, so itcan be solved with Mo’s Algorithm.