啊哈！线性基！
当然重点是如何处理换根部分，顺带记录一下有关线性基的东西。
- \(n\) 个数的线性基：构造 \(O(n\log a_i)\)，合并 \(O(\log^2a_i)\)，查询 \(O(\log a_i)\)。
以 \(1\) 为根，首先跑出欧拉序，预处理出每个点 \(u\) 子树的线性基 \(o[u]\)。这部分可以从子树上合并，复杂度 \(O(m\log^2 a_i)=O(n\log^2a_i)\)。
对于每一组询问 \((r,v)\)：
- \(r=v\)，此时答案就是 \(o[1]\) 的答案。
- \(v\) 不是 \(r\) 祖先，此时答案就是 \(o[v]\)。
- \(v\) 是 \(r\) 祖先。
第三种情况的话，我们可以找出一个节点 \(c\)，使得 \(c\) 在 \(r\) 到 \(v\) 的路径上且 \(dep[c]=dep[v]+1\)。
易得以 \(r\) 为根时 \(v\) 的子树中的点就是所有点除掉 以 \(1\) 为根时 \(c\) 的子树中的点 后的点。
那么对应的点在欧拉序上是一段前缀+一段后缀
于是处理一个欧拉序上的前缀线性基和后缀线性基，合并一下就好了。
btw，找 \(c\) 可以离线然后维护祖先栈 \(st\)，那么 \(c=st[dep[v]+1]\)。
标签：子树,CF1778E,log,dep,Tree,线性,Fallen,欧拉,根时 From： https://www.cnblogs.com/jimmywang/p/17093808.html