啊哈!线性基!
当然重点是如何处理换根部分,顺带记录一下有关线性基的东西。
- \(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