题目传送门前置知识树链剖分|线段树解法树剖换根，子树查询板子。类似换根DP的思路，我们发现换根后仅有祖先、子树、深度等会随祖先的变化而变化。设\(rt_{i}\)表示第\(i\)次操作的树根，\(x_{i}\)表示第\(i\)次操作的节点。接着进行大力分讨。当\(rt_{i}=x_{i}\)