虚树总结数据结构与算法qq44684888的博客-

**~~

虚树总结

**~~
** 用来优化树形dp的一种数据结构 所以树形dp得先会写不然优化个空气
题目大多具有对询问点总数有限制这个特征。算法本身思想是对于一些询问点，原树整体dp复杂度为o（n）（n为原树节点数量） 但原树上非询问节点实际上并非都需考虑，此时用虚树，只考虑询问点与部分其他点（询问点的LCA，用这些点建虚树再进行dp，多余的点压缩在链上，便可将复杂度降下来。对包含k个询问点的询问，所建虚树点数<=2*n
算法具体过程此处略过，https://www.luogu.com.cn/problemnew/solution/P2495这里的题解里有个人讲的挺好的，有兴趣可以看一下。
下面放模板

#define Reps(s) for(int i=Head[s],v=E[i].to;i;i=E[i].nxt,v=E[i].to)//虚树使用 const int MAX_N=; const int LG=;//log(MAX_N) struct Edge{int to,nxt;}e[MAX_N<<1],E[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;} int root,lg; int idx,dfn[MAX_N],siz[MAX_N],dep[MAX_N],fa[MAX_N][LG+2]; void dfs(int u) {     dfn[u]=++idx,siz[u]=1; repi(i,1,lg) fa[u][i]=fa[fa[u][i-1]][i-1]; reps(u)if(v!=fa[u][0]){         fa[v][0]=u,dep[v]=dep[u]+1; dfs(v),siz[u]+=siz[v]; } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); repd(j,lg,0)if(dep[fa[u][j]]>=dep[v]&&fa[u][j]) u=fa[u][j]; if(u==v) return u; repd(j,lg,0)if(fa[u][j]!=fa[v][j]&&fa[u][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } int a[MAX_N],A[MAX_N],rt; bool cmp(int x,int y){return dfn[x]<dfn[y];} int S[MAX_N],Top; int Head[MAX_N],Tote; void Add_edge(int u,int v){E[++Tote].to=v,E[Tote].nxt=Head[u];Head[u]=Tote;} void build_VT(int n) {//模板中虚树连的边是根到子节点的单向边，注意如果因题目需求虚树连的双向边，dfs的dp和dfs_clear函数都要注意判断不能走回边 sort(a+1,a+1+n,cmp);     S[Top=1]=a[1]; repi(i,2,n){ int x=a[i],y=lca(x,S[Top]); while(Top>1&&dep[y]<=dep[S[Top-1]]) Add_edge(S[Top-1],S[Top]),Top--; if(S[Top]!=y) Add_edge(y,S[Top]),S[Top]=y;         S[++Top]=x; } while(Top>1) Add_edge(S[Top-1],S[Top]),Top--;     rt=S[1]; } void dfs_clear(int u){Reps(u) dfs_clear(v);Head[u]=0;} void init(int n) { repi(i,0,n) head[i]=Head[i]=0;     tote=Tote=idx=0;     lg=log2(n)+1; } /*     init(n);     fa[root][0]=0,dep[root]=1;     dfs(root);     //询问点     int m; si(m);     repi(i,1,m) si(a[i]),A[i]=a[i];     build_VT(m);     Tote=0,dfs_clear(rt);     return 0; */ 

复杂度o(nlogn) ，建树o（klogk）（这里k为询问点的数量），建树处的log可以去掉，方法是用ST表求LCA代替（不过ST表预处理的常数要大一些，反正结果差不了多少倍增又好些为什么不倍增呢 ）

例题：
1.P2495 https://www.luogu.com.cn/problem/P2495
先建虚树，当然这题有特殊的地方，如果一个询问点为根的子树中也有询问点，那么子树中的点实际上不用考虑，所以建树就省了一点
考虑对一个虚树上的点，如果它本身是一个询问点，那么切掉该点的最小耗费即为该点到根路径的最小权，若不是，就是~最小权或切到子树询问点的最小耗费和，dp即可

typedef long long ll; const int MAX_N=5e5+5; const ll inf=4e18; int n,m; int a[MAX_N]; struct Edge{ int to,nxt;  ll w; }e[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v,ll w) {  e[++tote].to=v,e[tote].w=w,e[tote].nxt=head[u];  head[u]=tote; } int fa[MAX_N],dep[MAX_N],siz[MAX_N],top[MAX_N],son[MAX_N]; int idx,dfn[MAX_N],rdfn[MAX_N]; bool cmp(int a,int b){return dfn[a]<dfn[b];} ll mn[MAX_N]; void dfs_1(int u,int pre) {  dep[u]=dep[pre]+1,fa[u]=pre,siz[u]=1; reps(u)if(e[i].to!=pre){ int v=e[i].to;   mn[v]=min(mn[u],e[i].w); dfs_1(v,u);   siz[u]+=siz[v]; if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v; } } void dfs_2(int u,int tp) {  top[u]=tp,dfn[u]=++idx,rdfn[dfn[u]]=u; if(son[u]==-1) return; dfs_2(son[u],tp); reps(u){ int v=e[i].to; if(v!=fa[u]&&v!=son[u]) dfs_2(v,v); } } int LCA(int x,int y) { while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y);   x=fa[top[x]]; } return dep[x]<dep[y]?x:y; } void init(int n) { repi(i,0,n) head[i]=0,son[i]=-1;  tote=idx=dep[0]=0; } vector<int> g[MAX_N]; int stk[MAX_N],tp; void insert(int x) { if(tp==1){stk[++tp]=x;return;} int lca=LCA(x,stk[tp]); if(lca==stk[tp]) return ;//该题特殊的地方，若x要被切掉那么其子树所有点也都要被切，切x的同时会把子树都切掉，故子树上的不用判 while(tp>1&&dfn[stk[tp-1]]>=dfn[lca]) g[stk[tp-1]].pb(stk[tp]),tp--; if(lca!=stk[tp]) g[lca].pb(stk[tp]),stk[tp]=lca;  stk[++tp]=x; } ll dfs(int s) { if(!g[s].size()) return mn[s];  ll sum=0; for(auto x:g[s]) sum+=dfs(x);  g[s].clear(); return min(sum,mn[s]); } int main() { si(n); init(n); repi(i,1,n-1){ int u,v; si(u),si(v);   ll w; sl(w); add_edge(u,v,w),add_edge(v,u,w); }  mn[1]=inf; dfs_1(1,0),dfs_2(1,1); si(m); while(m--){ int k; si(k); repi(i,1,k) si(a[i]); sort(a+1,a+k+1,cmp);   stk[tp=1]=dfn[1]; repi(i,1,k) insert(a[i]); while(tp>0) g[stk[tp-1]].pb(stk[tp]),tp--; printf("%lldn",dfs(1)); } return 0; } 

2. P3233 https://www.luogu.com.cn/problem/P3233
   建虚树，先两遍dfs处理出距离每个点最近的管辖处及距离。后考虑对于一个虚树上的点u，对原树中u的儿子v，以其为根的子树若不包含管辖点，则整颗子树归管辖u的点管辖，倍增找到每个儿子减去其大小。最后处理虚树链上的点。对于一条边，若两端点属于同一块，直接加入即可，若不同，求出中间点的深度，倍增找到中间点后分别加入对应块。

using namespace std; typedef pair<int,int> P; const int inf=1e9; const int MAX_N=3e5+5; const int LG=18; struct Edge{int to,nxt;}e[MAX_N<<1],E[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;} int idx,dfn[MAX_N],siz[MAX_N],dep[MAX_N],fa[MAX_N][LG+2]; int dfs(int u) {  dfn[u]=++idx,siz[u]=1; reps(u)if(v!=fa[u][0]){   fa[v][0]=u,dep[v]=dep[u]+1; dfs(v),siz[u]+=siz[v]; } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); repd(j,LG,0)if(dep[fa[u][j]]>=dep[v]&&fa[u][j]) u=fa[u][j]; if(u==v) return u; repd(j,LG,0)if(fa[u][j]!=fa[v][j]&&fa[u][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } int a[MAX_N],A[MAX_N],rt; bool cmp(int x,int y){return dfn[x]<dfn[y];} int S[MAX_N],Top; int Head[MAX_N],Tote; void Add_edge(int u,int v){E[++Tote].to=v,E[Tote].nxt=Head[u];Head[u]=Tote;} void build_VT(int n) { sort(a+1,a+1+n,cmp);  S[Top=1]=a[1]; repi(i,2,n){ int x=a[i],y=lca(x,S[Top]); while(Top>1&&dep[y]<=dep[S[Top-1]]) Add_edge(S[Top-1],S[Top]),Top--; if(S[Top]!=y) Add_edge(y,S[Top]),S[Top]=y;   S[++Top]=x; } while(Top>1) Add_edge(S[Top-1],S[Top]),Top--;  rt=S[1]; } bool vis[MAX_N]; P g[MAX_N];// g[u].fi表示管辖u的点和与u的对应距离 void dfs_1(int u) { if(vis[u]) g[u]=P(0,u); else g[u]=P(inf,0); Reps(u) dfs_1(v),g[u]=min(g[u],P(g[v].fi+dep[v]-dep[u],g[v].se)); }//先从子树中确定 void dfs_2(int u,int d,int x) { if(P(d,x)<g[u]) g[u]=P(d,x); else d=g[u].fi,x=g[u].se; Reps(u) dfs_2(v,d+dep[v]-dep[u],x); }//再由上面的节点更新，看是否存在上面的更近的情况 int belong[MAX_N],up[MAX_N]; int ans[MAX_N]; void dfs_3(int u) {  belong[u]=g[u].se;  ans[belong[u]]+=siz[u]; Reps(u){ int x=v; repd(j,LG,0)if(fa[x][j]&&dep[fa[x][j]]>dep[u]) x=fa[x][j];   ans[belong[u]]-=siz[up[v]=x],dfs_3(v); } }//若u是虚树的点，对原树中u的儿子v，以其为根的子树若不包含管辖点，则整颗子树归管辖u的点管辖 void dfs_4(int u) { Reps(u){ int x=up[v],y=v; if(belong[u]==belong[v]) ans[belong[u]]+=siz[x]-siz[v];//两端归属点相同，直接加进去 else{//不同，算出中间点深度，倍增找到中间点分别加入 int H=dep[belong[v]]+dep[u]-g[u].fi;     H=H&1?H+1>>1:(belong[v]<belong[u]?H>>1:(H>>1)+1); repd(j,LG,0)if(fa[y][j]&&dep[fa[y][j]]>=H) y=fa[y][j];    ans[belong[v]]+=siz[y]-siz[v];    ans[belong[u]]+=siz[x]-siz[y]; } dfs_4(v); } }//讨论虚树压缩掉的链上的点 void dfs_clear(int u){Reps(u) dfs_clear(v);Head[u]=0;}//清树 void init(int n) { repi(i,0,n) head[i]=Head[i]=0;  tote=Tote=idx=fa[1][0]=dep[1]=0; } int main() { int n; si(n); init(n); repi(i,1,n-1){ int u,v; si(u),si(v); add_edge(u,v),add_edge(v,u); } dfs(1); repi(j,1,LG)repi(i,1,n) fa[i][j]=fa[fa[i][j-1]][j-1]; int q; si(q); while(q--){ int m; si(m); repi(i,1,m) si(a[i]),A[i]=a[i],vis[a[i]]=true; build_VT(m); dfs_1(rt); dfs_2(rt,g[rt].fi,g[rt].se); dfs_3(rt),dfs_4(rt);   ans[belong[rt]]+=siz[1]-siz[rt]; repi(i,1,m) printf("%d%c",ans[A[i]],ce(i,m));   Tote=0,dfs_clear(rt); repi(i,1,m) vis[a[i]]=ans[a[i]]=0; } return 0; } 

3. ICPC North Central NA Contest 2018-A https://nanti.jisuanke.com/t/45020
   输入的串建Tire，记录每个名字末端对应Trie的节点标号,。后对每次询问，以对应所有名字末端点关键点建虚树，设这些点值为1，向上更新，每个节点值为子节点值求和，答案即为所有值为询问l的点的总数，（虚树链上的点和该链底端的那个点的sum值相同）

typedef long long ll; const int MAX_N=5e5+5; const int LG=18;//log(MAX_N)  struct Edge{int to,nxt;}e[MAX_N<<2],E[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;} struct Tire{//?????????????,map??????,???? int ch[MAX_N][26];//2e6 64MB int siz; int insert(char *s) { int len=strlen(s+1); int u=1; repi(i,1,len){ int id=s[i]-'a';//????? ??a??0 if(!ch[u][id]) ch[u][id]=++siz,ms(ch[siz]);    u=ch[u][id]; } return u; } void init() { ms(ch[1]),siz=1; } }tire; void build_tree(int s) { repi(i,0,25)if(tire.ch[s][i]) add_edge(s,tire.ch[s][i]),add_edge(s,tire.ch[s][i]),build_tree(tire.ch[s][i]); } int root,lg; int idx,dfn[MAX_N],siz[MAX_N],dep[MAX_N],fa[MAX_N][25]; void dfs(int u) { pr(u);     dfn[u]=++idx,siz[u]=1; repi(i,1,lg) fa[u][i]=fa[fa[u][i-1]][i-1]; reps(u)if(v!=fa[u][0]){         fa[v][0]=u,dep[v]=dep[u]+1; dfs(v),siz[u]+=siz[v]; } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); repd(j,lg,0)if(dep[fa[u][j]]>=dep[v]&&fa[u][j]) u=fa[u][j]; if(u==v) return u; repd(j,lg,0)if(fa[u][j]!=fa[v][j]&&fa[u][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } int a[MAX_N],A[MAX_N],rt; bool cmp(int x,int y){return dfn[x]<dfn[y];} int S[MAX_N],Top; int Head[MAX_N],Tote; void Add_edge(int u,int v){E[++Tote].to=v,E[Tote].nxt=Head[u];Head[u]=Tote;} void build_VT(int n) { sort(a+1,a+1+n,cmp);  S[Top=1]=a[1]; repi(i,2,n){ int x=a[i],y=lca(x,S[Top]); while(Top>1&&dep[y]<=dep[S[Top-1]]) Add_edge(S[Top-1],S[Top]),Top--; if(S[Top]!=y) Add_edge(y,S[Top]),S[Top]=y;   S[++Top]=x; } while(Top>1) Add_edge(S[Top-1],S[Top]),Top--;  rt=S[1]; } bool vis[MAX_N]; int dp[MAX_N],ans; void dfs_1(int u,int l) {  dp[u]=vis[u]; Reps(u){ dfs_1(v,l);   dp[u]+=dp[v]; if(dp[v]==l) ans+=dep[v]-dep[u]; } } void dfs_clear(int u){Reps(u) dfs_clear(v);Head[u]=0;} void init(int n) { repi(i,0,n) head[i]=Head[i]=0;     tote=Tote=idx=0;     lg=log2(n)+1; } char s[MAX_N]; int pos[MAX_N]; int main() { int n,q; si(n),si(q);  tire.init(); repi(i,1,n){ ss(s+1);   pos[i]=tire.insert(s); } init(tire.siz);  root=1; build_tree(root);  fa[root][0]=0,dep[root]=1; dfs(root); while(q--) { int k,l; si(k),si(l); repi(i,1,k) si(a[i]),a[i]=pos[a[i]],vis[a[i]]=true; build_VT(k);   ans=0; dfs_1(rt,l); if(dp[rt]==l&&rt!=root) ans+=dep[rt]-dep[root]; printf("%dn",ans);   Tote=0,dfs_clear(rt); repi(i,1,k) vis[a[i]]=false; } return 0; } 

4.血压游戏 https://ac.nowcoder.com/acm/problem/205300
取同深度的点分别建虚树，dp即可

typedef long long ll; const int MAX_N=2e5+5; const int LG=18;//log(MAX_N) struct Edge{int to,nxt;}e[MAX_N<<1],E[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;}     ll b[MAX_N]; int root,lg; int idx,dfn[MAX_N],siz[MAX_N],dep[MAX_N],fa[MAX_N][LG+2]; vector<int> rec[MAX_N]; void dfs(int u) {     rec[dep[u]].pb(u);     dfn[u]=++idx,siz[u]=1; repi(i,1,lg) fa[u][i]=fa[fa[u][i-1]][i-1]; reps(u)if(v!=fa[u][0]){         fa[v][0]=u,dep[v]=dep[u]+1; dfs(v),siz[u]+=siz[v]; } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); repd(j,lg,0)if(dep[fa[u][j]]>=dep[v]&&fa[u][j]) u=fa[u][j]; if(u==v) return u; repd(j,lg,0)if(fa[u][j]!=fa[v][j]&&fa[u][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } int a[MAX_N],A[MAX_N],rt; bool cmp(int x,int y){return dfn[x]<dfn[y];} int S[MAX_N],Top; int Head[MAX_N],Tote; void Add_edge(int u,int v){E[++Tote].to=v,E[Tote].nxt=Head[u];Head[u]=Tote;} void build_VT(int n) { sort(a+1,a+1+n,cmp);     S[Top=1]=a[1]; repi(i,2,n){ int x=a[i],y=lca(x,S[Top]); while(Top>1&&dep[y]<=dep[S[Top-1]]) Add_edge(S[Top-1],S[Top]),Top--; if(S[Top]!=y) Add_edge(y,S[Top]),S[Top]=y;         S[++Top]=x; } while(Top>1) Add_edge(S[Top-1],S[Top]),Top--;     rt=S[1]; } ll dp[MAX_N]; void dfs_1(int u,int md) { if(dep[u]==md){         dp[u]=b[u];return; }     dp[u]=0; Reps(u){ dfs_1(v,md); if(dp[v]) dp[u]+=max(1ll,dp[v]-(dep[v]-dep[u])); } } void dfs_clear(int u){Reps(u) dfs_clear(v);Head[u]=0;} void init(int n) { repi(i,0,n) head[i]=Head[i]=0;     tote=Tote=idx=0;     lg=log2(n)+1; } int main() { int n; si(n),si(root); init(n); repi(i,1,n) sl(b[i]); repi(i,1,n-1){ int u,v; si(u),si(v); add_edge(u,v),add_edge(v,u); }     fa[root][0]=0,dep[root]=1; dfs(root);     ll ans=0; repi(i,1,n)if(rec[i].size()){ int m=rec[i].size(); repi(j,1,m) a[j]=rec[i][j-1]; build_VT(m); dfs_1(rt,i); if(dp[rt]) ans+=max(1ll,dp[rt]-(dep[rt]-dep[root])-1);         Tote=0,dfs_clear(rt); } printf("%lldn",ans); return 0; } 

5.王国 https://ac.nowcoder.com/acm/contest/5403/C
取相同归属的点建虚树后求出虚树的直径后平方取最大值即可（考虑虚树的特性，不可能为根到叶子节点为直径）
听队友说这题暴力枚举相同归属点的点n^2logn能过？？

typedef long long ll; const int MAX_N=1e5+5;; const int LG=18;//log(MAX_N) struct Edge{int to,nxt;}e[MAX_N<<1],E[MAX_N<<1]; int head[MAX_N],tote; void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;} int root,lg; int idx,dfn[MAX_N],siz[MAX_N],dep[MAX_N],fa[MAX_N][LG+2]; void dfs(int u) {     dfn[u]=++idx,siz[u]=1; repi(i,1,lg) fa[u][i]=fa[fa[u][i-1]][i-1]; reps(u)if(v!=fa[u][0]){         fa[v][0]=u,dep[v]=dep[u]+1; dfs(v),siz[u]+=siz[v]; } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); repd(j,lg,0)if(dep[fa[u][j]]>=dep[v]&&fa[u][j]) u=fa[u][j]; if(u==v) return u; repd(j,lg,0)if(fa[u][j]!=fa[v][j]&&fa[u][j]) u=fa[u][j],v=fa[v][j]; return fa[u][0]; } int a[MAX_N],A[MAX_N],rt; bool cmp(int x,int y){return dfn[x]<dfn[y];} int S[MAX_N],Top; int Head[MAX_N],Tote; void Add_edge(int u,int v){E[++Tote].to=v,E[Tote].nxt=Head[u];Head[u]=Tote;} void build_VT(int n) { sort(a+1,a+1+n,cmp);     S[Top=1]=a[1]; repi(i,2,n){ int x=a[i],y=lca(x,S[Top]); while(Top>1&&dep[y]<=dep[S[Top-1]]) Add_edge(S[Top-1],S[Top]),Add_edge(S[Top],S[Top-1]),Top--; if(S[Top]!=y) Add_edge(y,S[Top]),Add_edge(S[Top],y),S[Top]=y;         S[++Top]=x; } while(Top>1) Add_edge(S[Top-1],S[Top]),Add_edge(S[Top],S[Top-1]),Top--;     rt=S[1]; } int ans; void dfs_1(int u,int fa,int dis) {  ans=max(ans,dis); Reps(u)if(v!=fa) dfs_1(v,u,dis+abs(dep[u]-dep[v])); } void dfs_clear(int u,int fa){Reps(u)if(v!=fa) dfs_clear(v,u);Head[u]=0;} void init(int n) { repi(i,0,n) head[i]=Head[i]=0;     tote=Tote=idx=0;     lg=log2(n)+1; } vector<int> bl[MAX_N]; int main() { int n; si(n); init(n); repi(i,1,n){ int x; si(x);   bl[x].pb(i); } repi(i,1,n-1){ int u,v; si(u),si(v); add_edge(u,v),add_edge(v,u); }  root=1;  fa[root][0]=0,dep[root]=1; dfs(root);  ans=0; repi(i,1,n)if(bl[i].size()){ int len=bl[i].size(); int mx=-1,st=-1; repi(j,1,len){    a[j]=bl[i][j-1]; if(dep[a[j]]>mx) mx=dep[a[j]],st=a[j]; } build_VT(len); dfs_1(st,0,0);   Tote=0,dfs_clear(rt,0); }; printf("%lldn",1ll*ans*ans); return 0; }