给定一个树 T 和一个树 T 上的点集 S,求
E_S=\bigcup_{i\in S}^n\bigcup_{j\in S}^n E(i,j)
其中 E(i,j) 表示点对(i,j)路径上的边集.
sol:
可以想到用 \rm LCA 来表征一条路径, 一条边 <u,v>出现在 E_S 中当且仅当 S 中存在点 i_1,i_2 分布在 u 的不同子树中 (假设 u 是 u,v 两点中深度较小的那个点).
假设一个点 u 是一个点集 S'(\subset S) 的所有点的 \rm LCA; v\in S, v\notin S', \exists x\in S', {\rm LCA}(v,x)=u, 即 x,v 在 u 的不同子树中, 若我们已知 S' 的点对路径并 E_{S'}, 那么加入点 v 之后，路径并即再添加 E(u,v), 此时 \forall i\in S', E(i,v) 必然分成了 E(i,u) 和 E(u,v) 两部分, 且 E(i,u) \subseteq E_{S'}, 因此 E_{S'}\bigcup E(u,v)=E_S
直观点说就是用前缀集合的 \rm LCA' 和新点 u 找\rm LCA(LCA',u) 然后迭代(归纳)的一个过程.
对于强制在线在 s 中动态插入删除 \forall x, 只需要考虑相邻 \rm dfn 序的点构成的集合并即可, 这里不再赘述.
给定树上点集合 S ，定义一个点集 S 的 \rm LCA 为 {\rm LCA}(S), 给出两种操作
- 插入一个点 x
- 删除一个点 x
- 求出 {\rm LCA}(S)
sol:
考虑 \rm LCA 的形成 :
引理 : 若 u = {\rm LCA}(S), 则 \forall v, v \in S, {\rm LCA}(u, v) = u
如果 S 中所有点的 \rm LCA:u\in S , 那么显然 u 和 \forall v, v\neq u, v \in S 的 \rm LCA 一定还是 u， 此时选取 u 和其他任意点 v 求\rm LCA 即可.
如果 u \notin S , 那么一定存在至少一对 <x,y> 使得 {\rm LCA}(x,y) = u , 因为 u 同时是 S 中所有点的 \rm LCA, 所以 dep_u < dep_v, \forall v, v \in S (若存在一个 v', v' \in S 使得 dep_{v'}= dep_u , 容易知道 dep_{{\rm LCA} (u,v')} \leq dep_u-1 , 与假设 u = {\rm LCA}(S) 不符) .
又因为若 u \notin S, dep_u < dep_v, \forall v, v \in S , dfn_u < \max_{v\in S} (dfn_v) , 亦即 \forall v, v \in S 在 u 的子树中.
考虑 {\rm LCA}(S) 在欧拉序上的定义, 容易知道 [\min (start_{u}), \max (start_{v})] 欧拉序区间上出现的最小点即为 {\rm LCA} (S), 其中 u, v 分别是 dfn 最小和最大的在 S 中的点, {\rm LCA}(u, v) = {\rm LCA} (S).
综上, 选取 S 中 dfn 最小和最大的两个点求 LCA 即为 {\rm LCA}(S)