前置知识：树的 dfs 序及其性质
参考：洛谷日报
定义
某棵树 \(T\) 上存在一个关键点点集 \(S\)。如果存在某个点集 \(T'\) 满足 \(S\subseteq T'\subseteq T\)，且 \(\forall u,v\in T',\operatorname{lca}(u,v)\in T'\)；则 \(T'\) 为关键点的一棵虚树。
虚树可以就是原树，但是为了能够更方便地统计所有关键点的信息，显然我们需要虚树的大小尽量小。
性质
显然虚树中的关键点的祖先后代关系不会变。
虚树的最少节点数不超过 \(2k-1\)。（\(k\) 为关键点数量）证明：考虑在原有虚树上不断加点的过程，每加入一个关键点最多不会加入一个 \(\text{lca}\)。（下面讨论的虚树即为这棵最小的虚树）
所有关键点按照 dfs 序排序后，（设排好序的点为 \(v_1,v_2,\cdots,v_k\)）则 \(v_1\rightarrow v_2,v_2\rightarrow v_3,\cdots,v_{k-1}\rightarrow v_k\) 的路径并刚好覆盖了虚树的所有点，且虚树的每个非关键点对应在路径并上只会是有多个子节点的点。
构造
考虑上述的第三条性质。可以在构造虚树时将关键点按照 dfn 排序，然后依次在虚树上加入上述 \(v_1\rightarrow v_2,v_2\rightarrow v_3,\cdots,v_{k-1}\rightarrow v_k\) 路径。考虑加入 \(v_1\sim v_{k-1}\) 后怎样加入 \(v_{k-1}\rightarrow v_k\)。可以在最开始时将根节点加入虚树，然后 \(\text{lca}(v_{k-1},v_k)\rightarrow v_{k-1}\) 部分已经在构建好的树内，只需要加入 \(\text{lca}\rightarrow v_k\) 部分即可。
我们可以用栈维护最后一个加入的节点到根节点的路径上存在于当前虚树的点，此时可以在新加入 \(v_k\) 前，将深度大于 \(\text{lca}\) 的点弹出；然后加入 \(\text{lca}\) 和 \(v_k\)。
注意：如果某个点被弹栈后，由 dfs 序性质可知其在栈中不会出现深度更浅的祖先节点，此时可以将其与栈中前驱连边，表示虚树中这个点的父亲已经确定（而上述操作中最后被弹出的点在虚树上的父亲为 \(\text{lca}\)）。
在加完所有点后，需要将栈中每个点弹出，同时执行上述的操作。
应用
如果对于某组关键点满足的性质在这组关键点的虚树上同样满足，则可以建立这组关键点的虚树，在虚树上解决问题。
例题1：CF613D Kingdom and its Cities
题意
有一棵大小为 \(n\) 的树。\(q\) 次询问，每次给出 \(k\) 个关键点，询问使得关键点两两不连通需要删除的最少 非关键点 数。\(n,q,\sum k\le 10^5\)。
解法
考虑无解的情况：如果某个关键点的父节点也是关键点，则显然无解。下面为了方便，只讨论有解的情况。
考虑使用归纳法。如果对于某个节点 \(u\) 的每个子节点对应的子树均使用了最优策略，则需要如何保证 \(u\) 子树也采用了最优策略。显然最优策略中 \(u\) 的每个儿子所在的连通块的关键点个数不超过 \(1\) 个。设 \(u\) 和所有儿子的连通块连通后有 \(S\) 个关键点。
若 \(S>1\)：\(u\) 为关键点，则需要删除 \(S-1\) 个点，与其的连通块中有关键点的儿子断开；\(u\) 非关键点，则只需要删除 \(u\) 即可，保证了 \(u\) 所在的连通块内关键点最少。
若 \(S\le 1\)，则不需要删点。即使这会导致 \(u\) 所在连通块内有关键点（而原本可以没有），但是由上述操作可知：将关键点留下来后对之后的答案减少的贡献不会超过 \(1\)；故最后不需要删点。（感觉不太严谨）
综上，我们可除了一组方法。然而单次求答案需要 dfs 整棵树，同时不需要考虑没有关键点的子树；故可以把上述操作搬到虚树上。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxl=20;
const int maxn=100010;
int n,i,j,u,v,t,q,k,tp,top,ans;
int lt[maxn],vn[maxn],vh[maxn];
int h[maxn],s[maxn],dfn[maxn],dep[maxn];
int lb[maxn<<1],eul[maxl][maxn<<1],stk[maxn];
bool sz[maxn];
struct edge{int to,nxt;}E[maxn<<1];
void dfs(int p,int f){
dfn[p]=++tp;
eul[0][tp]=p;
dep[p]=dep[f]+1;
int lp,to;
for(lp=h[p];lp;lp=E[lp].nxt){
to=E[lp].to;
if(to==f) continue;
dfs(to,p); eul[0][++tp]=p;
}
}
inline int lca(int x,int y){
if(!y) return x;
x=dfn[x], y=dfn[y];
if(x>y) swap(x,y);
int le=lb[y-x+1];
int ld=eul[le][x],rd=eul[le][y-(1<<le)+1];
if(dep[ld]>dep[rd]) return rd; return ld;
}
inline bool cmp(const int &x,const int &y){return dfn[x]<dfn[y];}
inline void add(int x,int y){
vn[y]=vh[x];
vh[x]=y;
}
void dfsv(int p){
int sm=(lt[p]==j);
for(int to=vh[p];to;to=vn[to]){
if(((lt[p]==j)&&(lt[to]==j))&&
(dep[to]-dep[p]==1)) ans=-maxn;
dfsv(to);
if(sz[to]) ++sm;
sz[to]=0;
}
if(sm>1){
if(lt[p]==j) ans+=sm-1,sz[p]=1;
else ++ans,sz[p]=0;
}
else if(sm==1) sz[p]=1;
else sz[p]=0; vh[p]=0;
}
int main(){
for(i=2;i<(maxn<<1);++i) lb[i]=lb[i>>1]+1;
scanf("%d",&n);
for(i=1;i<n;++i){
scanf("%d%d",&u,&v);
E[++t]={v,h[u]};h[u]=t;
E[++t]={u,h[v]};h[v]=t;
}
dfs(1,0);
for(j=1;j<maxl;++j){
for(i=(1<<(j-1))+1;i<=tp;++i){
u=eul[j-1][i-(1<<(j-1))];
v=eul[j-1][i];
if(dep[u]>dep[v]) u=v;
eul[j][i-(1<<(j-1))]=u;
}
}
scanf("%d",&q);
for(j=1;j<=q;++j){
scanf("%d",&k);
for(i=1;i<=k;++i) scanf("%d",s+i);
sort(s+1,s+k+1,cmp); stk[1]=top=1;
for(i=1;i<=k;++i){
u=s[i], v=lca(u,s[i-1]);
while(dep[stk[top-1]]>dep[v]){
add(stk[top-1],stk[top]);
--top;
}
if(dep[stk[top]]>dep[v]){
add(v,stk[top]);
--top;
}
if(v!=stk[top]) stk[++top]=v;
if(u!=stk[top]) stk[++top]=u;
lt[u]=j;
}
if(i<=k) continue;
while(top){
add(stk[top-1],stk[top]);
--top;
}
ans=0; dfsv(1); sz[1]=0;
if(ans<0) ans=-1;
printf("%d\n",ans);
}
return 0;
}
例题2
题意
有一棵大小为 \(n\) 的树，\(q\) 组询问，每次给出 \(k\) 个关键点，求离每个关键点最近的关键点的距离。
解法
可以把 \(dis(u,v)\) 拆成 \(dep_u+(dep_v-2dep_{\text{lca}(u,v)})\)，然后记 \(f_u\) 为离 \(u\) 最近的后代关键点与 \(u\) 的距离减 \(dep_u\)（可能为自身），\(g_u\) 类似但是关键点可以为 \(u\)。此时考虑 \(u\) 和最近关键点的 \(\text{lca}\) 并在 \(\text{lca}\) 处统计距离。如果 \(\text{lca}=u\) 则答案为 \(dep_u+f_u\)；否则答案为 \(dep_u+\min_{u\in Tree_v,u\ne v}g_u\)。求 \(\min_{u\in Tree_v,u\ne v}g_u\)，\(f\) 和 \(g\) 可以用 dfs 求。
同样可以发现只有关键点的虚树上的点时需要的，所以只需要建虚树再按照以上流程操作即可。
例题3
题意
有一棵大小为 \(n\) 的树，\(q\) 次询问，每次求某个点 \(u\) 到 \([l,r]\) 内点的最短距离。\(n,q\le 10^5\)。
解法
首先考虑 \([l,r]\) 固定时怎么做。做法和上述内容类似，但是需要将 \(u\) 同时加入虚树中。
至于涉及多个 \([l,r]\) 时，可以使用线段树分治，将每个 \([l,r]\) 拆分成 \(O(\log)\) 个线段树上的区间即可。
例题4
题意
给定一棵树和若干个关键点 \(u_1,u_2,\cdots,u_k\)，你需要维护这个关键点集，支持：
- 加入一个点。
- 删除一个点。
- 求从根节点出发，经过一条路径遍历所有的关键点，路径长度的最小值。
要求 \(O(q\log n)\)。强制在线。
解法
考察到了 dfs 序的一个性质：树上按照 dfs 序排好的点 \(u_1,u_2,\cdots,u_k\)，其中 \(u_1\rightarrow u_2,u_2\rightarrow u_3,\cdots,u_{k-1}\rightarrow u_k,u_k\rightarrow u_1\) 所有路径刚好覆盖了 \(u_1\sim u_k\) 形成的最小连通子树，其中每条边均被覆盖了两次。可以用权值线段树/平衡树维护这些路径总长。然而求的是从根节点出发的路径长度，需要这个连通子树的根节点，而这个根节点可以使用欧拉序 + 权值线段树/平衡树在线求。