上次的被吃掉啦，这回加深了对虚树的理解再补发一下

虚树大概就是选出树上m个点，对m个点的DFS序排序，建出最多2m个点的树就是虚树，在虚树上可以解决一些问题

一、动态统计问题

这类问题一般都比较裸，联通所选所有点所需长度=（DFS相邻点间距离+DFS首尾距离）/2，然后直接上个set就秒了

ZHOJ1910castles 虚树解决动态统计问题的裸题

#include<cstdio>
#include<iostream>
#include<set>
#define N 111111
#define inf 1e9
using namespace std;
set<int> st;
int n,k,i,x,y,u,l,r,tot,sz,ans,tmp,now,head,id[N],pos[N],high[N],fir[N],la[N<<1],ne[N<<1],fa[N][17];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int z){
    id[x]=++sz;pos[sz]=x;
    for(int i=1;i<=16;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=fir[x];i;i=ne[i]){
        int y=la[i];
        if(y!=z){
            high[y]=high[x]+1;
            fa[y][0]=x;
            dfs(y,x);
        }
    }
}
int lca(int x,int y){
    if(high[x]<high[y])swap(x,y);
    int t=high[x]-high[y];
    for(int i=0;i<=14;i++)if(t&(1<<i))x=fa[x][i];
    for(int i=14;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;else return fa[x][0];
}
int dis(int x,int y){return high[x]+high[y]-2*high[lca(x,y)];}
void change(int i,int f){
    int l=*--st.lower_bound(id[i]),r=*st.upper_bound(id[i]);
    if(r!=inf)ans+=f*dis(i,pos[r]);
    if(l!=-inf)ans+=f*dis(i,pos[l]);
    if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
    if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
    now=1+((ans+tmp)>>1);
}
int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
    dfs(1,0);st.insert(inf);st.insert(-inf);
    for(i=1;i<=n;i++){
        st.insert(id[i]);
        change(i,1);
        while(now>k){
            st.erase(id[++head]);
            change(head,-1);
        }
        if(i-head>u)u=i-head;
    }
    printf("%d",u);
}

BZOJ3991寻宝游戏 又是一道裸题

#include<cstdio>
#include<iostream>
#include<set>
#define N 111111
#define inf 1e9
using namespace std;
set<int> st;
int n,m,k,i,x,y,z,u,l,r,f,tot,sz,now,head,id[N],pos[N],high[N],fir[N],val[N<<1],la[N<<1],ne[N<<1],fa[N][18];
long long ans,tmp,deep[N];
bool mark[N];
void ins(int x,int y,int z){la[++tot]=y;val[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int z){
	id[x]=++sz;pos[sz]=x;
	for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(y!=z){
			deep[y]=deep[x]+val[i];
			high[y]=high[x]+1;
			fa[y][0]=x;
			dfs(y,x);
		}
	}
}
int lca(int x,int y){
	if(high[x]<high[y])swap(x,y);
	int t=high[x]-high[y];
    for(int i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
    for(int i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;else return fa[x][0];
}
long long dis(int x,int y){return deep[x]+deep[y]-2*deep[lca(x,y)];}
void change(int i,int f){
	int l=*--st.lower_bound(id[i]),r=*st.upper_bound(id[i]);
	if(r!=inf)ans+=f*dis(i,pos[r]);
	if(l!=-inf)ans+=f*dis(i,pos[l]);
	if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
	if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
	now=1+((ans+tmp)>>1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	dfs(1,0);st.insert(inf);st.insert(-inf);
	while(m--){
		scanf("%d",&x);
		if(mark[x])st.erase(id[x]),f=-1;
		else st.insert(id[x]),f=1;
		mark[x]^=1;
		int l=*--st.lower_bound(id[x]),r=*st.upper_bound(id[x]);
		if(r!=inf)ans+=f*dis(x,pos[r]);
		if(l!=-inf)ans+=f*dis(x,pos[l]);
		if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
		if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
		printf("%lld\n",ans+tmp);
	}
}

2015多校第一场1009 还是一道裸题

#include<cstdio>
#include<iostream>
#include<set>
#include<cstring> 
#define N 222222
#define inf 1e16
using namespace std;
set<long long> st;
long long T,p,n,m,k,i,x,y,z,u,l,r,f,tot,sz,now,head,cas,id[N],pos[N],high[N],fir[N],val[N<<1],la[N<<1],ne[N<<1],fa[N][18];
long long ans,tmp,deep[N];
bool mark[N];
void ins(long long x,long long y,long long z){la[++tot]=y;val[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(long long x,long long z){
    id[x]=++sz;pos[sz]=x;
    for(long long i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
    for(long long i=fir[x];i;i=ne[i]){
        long long y=la[i];
        if(y!=z){
            deep[y]=deep[x]+val[i];
            high[y]=high[x]+1;
            fa[y][0]=x;
            dfs(y,x);
        }
    }
}
long long lca(long long x,long long y){
    if(high[x]<high[y])swap(x,y);
    long long t=high[x]-high[y];
    for(long long i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
    for(long long i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;else return fa[x][0];
}
long long dis(long long x,long long y){return deep[x]+deep[y]-2*deep[lca(x,y)];}
void change(long long i,long long f){
    long long l=*--st.lower_bound(id[i]),r=*st.upper_bound(id[i]);
    if(r!=inf)ans+=f*dis(i,pos[r]);
    if(l!=-inf)ans+=f*dis(i,pos[l]);
    if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
    if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;
    now=1+((ans+tmp)>>1);
}
int main(){
    scanf("%I64d",&T);
    while(T--){
        printf("Case #%lld:\n",++cas);
        memset(mark,0,sizeof(mark));
        memset(pos,0,sizeof(pos));
        memset(fir,0,sizeof(fir));
        memset(fa,0,sizeof(fa));
        memset(deep,0,sizeof(deep));
        memset(ne,0,sizeof(ne));
        memset(val,0,sizeof(val));
        memset(la,0,sizeof(la));
        memset(id,0,sizeof(id));
        st.clear();ans=0;tmp=0;
        sz=0;tot=0;
    scanf("%I64d%I64d",&n,&m);
    for(i=1;i<n;i++)scanf("%I64d%I64d%I64d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
    dfs(1,0);st.insert(inf);st.insert(-inf);
    while(m--){
        scanf("%I64d%I64d",&p,&x);
        f=0;
        if(p==1){
            if(!mark[x])st.insert(id[x]),f=1;
            mark[x]=1;
        }else{
            if(mark[x])st.erase(id[x]),f=-1;
            mark[x]=0;
        }
        if(f){
        long long l=*--st.lower_bound(id[x]),r=*st.upper_bound(id[x]);
        if(r!=inf)ans+=f*dis(x,pos[r]);
        if(l!=-inf)ans+=f*dis(x,pos[l]);
        if(l!=-inf&&r!=inf)ans-=f*dis(pos[l],pos[r]);
        if(st.size()!=2)tmp=dis(pos[*st.upper_bound(-inf)],pos[*--st.lower_bound(inf)]);else tmp=0;}
        printf("%I64d\n",(ans+tmp)/2);
    }
    }
}

二、DP问题

这时候一般要建立出一颗虚树，可以按DFS序排序后，用维护一个单调栈的方法建立

for(i=1;i<=m;i++){
			int x=a[i],y;
			if(!top)father[x]=0;else{//构建虚树 
				for(y=lca(x,stack[top]),father[x]=y;high[stack[top]]>high[y];top--)if(high[stack[top-1]]<=high[y])father[stack[top]]=y;
				if(stack[top]!=y){
					father[y]=stack[top];
					stack[++top]=y;
					near[y]=mp(inf,0);
					tree[++mxh]=y;
				}
			}
			stack[++top]=x;
		}

也可以排两遍序建立

   for(scanf("%d",&m),A=tot=0,A1=1e9,A2=-1e9,v[1]=a[1]=1,t=++m,i=2;i<=m;i++)scanf("%d",&a[i]),v[a[i]]=V[a[i]]=1;
   for(sort(a+1,a+m+1,cmp),i=1;i<m;i++)if(!v[x=lca(a[i],a[i+1])])v[a[++t]=x]=1;
   for(m=t,sort(a+1,a+m+1,cmp),ed=0,q[t=1]=1,i=2;i<=m;ins(q[t],a[i]),q[++t]=a[i++])for(;st[a[i]]<st[q[t]]||en[a[i]]>en[q[t]];t--);
   for(dfs(i=1),printf("%lld %d %d\n",A,A1,A2);i<=m;i++)v[a[i]]=V[a[i]]=fir[a[i]]=0;

SDOI2011消耗战 比较简单的虚树DP

#include<cstdio>
#include<algorithm>
#include<iostream>
#define inf 1e15
#define N 266666
using namespace std;
int n,m,k,i,x,y,top,tot,tot2,sz,w,h[N],pos[N],deep[N],stack[N],first[N],last[N<<1],next[N<<1],next2[N<<1],last2[N<<1],fa[N][18];
long long z,value[N<<1],f[N],mn[N],first2[N];
bool cmp(int a,int b){return pos[a]<pos[b];}
void ins(int x,int y,long long z){last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;}
void ins2(int x,int y){if(x==y)return;last2[++tot]=y;next2[tot]=first2[x];first2[x]=tot;}
void dfs(int x){
	pos[x]=++sz;
	for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa[x][0]){
			mn[y]=min(mn[x],value[i]);
			deep[y]=deep[x]+1;
			fa[y][0]=x;
			dfs(y);
		}
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	int t=deep[x]-deep[y];
    for(int i=0;i<=17;i++)if(t&(1<<i))x=fa[x][i];
    for(int i=17;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;else return fa[x][0];
}
void dp(int x){
	f[x]=mn[x];
	long long tmp=0;
	for(int i=first2[x];i;i=next2[i]){
		dp(last2[i]);
		tmp+=f[last2[i]];
	}
	first2[x]=0;
	if(!tmp)f[x]=mn[x];else if(tmp<=f[x])f[x]=tmp;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d%lld",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	mn[1]=inf;dfs(1);
	scanf("%d",&m);
	while(m--){
		scanf("%d",&k);
		for(i=1;i<=k;i++)scanf("%d",&h[i]);
		sort(h+1,h+k+1,cmp);
    	h[w=1]=h[1];tot=0;
    	for(i=2;i<=k;i++)if(lca(h[w],h[i])!=h[w])h[++w]=h[i];
		stack[++top]=1;
		for(i=1;i<=w;i++){
			int now=h[i],t=lca(now,stack[top]);
			while(deep[t]<deep[stack[top]]){
				if(deep[t]>=deep[stack[top-1]]){
					ins2(t,stack[top--]);
					if(stack[top]!=t)stack[++top]=t;
					break;
				}
				ins2(stack[top-1],stack[top]),top--;
			}
			if(stack[top]!=now)stack[++top]=now;
		}
		while(--top)ins2(stack[top],stack[top+1]);
		dp(1);
		printf("%lld\n",f[1]);
	}
}

HEOI2014大工程 建出虚树后直接DP就可以了

#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;LL A,g[N];bool v[N],V[N];int T,m,n,x,y,i,tot,id,ed,t,A1,A2,a[N],q[N],mi[N],mx[N],fir[N],st[N],d[N],f[N],F[N][20],ne[N<<1],la[N<<1],en[N];
bool cmp(int x,int y){return st[x]<st[y];}
void ins(int x,int y){if(x!=y)la[++tot]=y,ne[tot]=fir[x],fir[x]=tot;}
void dfs(int x,int fa){
	st[x]=++id;int i,y;for(i=1;i<=19;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)d[y=la[i]]=d[x]+1,F[y][0]=x,dfs(y,x);en[x]=id;
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);int t=d[x]-d[y],i;
    for(i=0;i<=19;i++)if(t>>i&1)x=F[x][i];
    for(i=19;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}
void dfs(int x){
	f[x]=V[x];g[x]=0;mi[x]=V[x]?0:1e9;mx[x]=V[x]?0:-1e9;
	for(int i=fir[x],y,o;i;i=ne[i])dfs(y=la[i]),o=d[y]-d[x],A+=(g[x]+1ll*f[x]*o)*f[y]+g[y]*f[x],f[x]+=f[y],g[x]+=g[y]+1ll*f[y]*o,A1=min(A1,mi[x]+mi[y]+o),A2=max(A2,mx[x]+mx[y]+o),mi[x]=min(mi[x],mi[y]+o),mx[x]=max(mx[x],mx[y]+o);
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1,0),memset(fir,0,sizeof(fir)),scanf("%d",&T);T--;){
		for(scanf("%d",&m),A=tot=0,A1=1e9,A2=-1e9,v[1]=a[1]=1,t=++m,i=2;i<=m;i++)scanf("%d",&a[i]),v[a[i]]=V[a[i]]=1;
		for(sort(a+1,a+m+1,cmp),i=1;i<m;i++)if(!v[x=lca(a[i],a[i+1])])v[a[++t]=x]=1;
		for(m=t,sort(a+1,a+m+1,cmp),ed=0,q[t=1]=1,i=2;i<=m;ins(q[t],a[i]),q[++t]=a[i++])for(;st[a[i]]<st[q[t]]||en[a[i]]>en[q[t]];t--);
		for(dfs(i=1),printf("%lld %d %d\n",A,A1,A2);i<=m;i++)v[a[i]]=V[a[i]]=fir[a[i]]=0;
	}
}

HNOI2014世界树 比较难的虚树DP，反正我是ydcydc才搞出来的的

HNOI2014世界树：#include<bits/stdc++.h>
#define N 300010
#define inf 1e9
#define mp make_pair
#define CL(a) memset(a,0,sizeof(a))
#define X first
#define Y second
using namespace std;
int n,m,i,x,y,Q,sz,tot,top,mxh,tmp[N],a[N],st[N],tree[N],fa[N],size[N],val[N],pos[N],in[N],fa[N][19],high[N],fir[N],ans[N],ne[N<<1],la[N<<1];
pair<int,int>near[N];
bool cmp(int x,int y){return pos[x]<pos[y];}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	size[x]=1;pos[x]=++sz;
	for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(fa[x][0]!=y){
			fa[y][0]=x;fa[y]=x;high[y]=high[x]+1;
			dfs(y);size[x]+=size[y];
		}
	}
}
int find(int x,int d){//找到x的深度为d的祖先
	for(int i=18;i>=0,high[x]>d;i--)if(high[fa[x][i]]>=d)x=fa[x][i];
	return x;
}
int lca(int x,int y){
    if(high[x]<high[y])swap(x,y);
    int t=high[x]-high[y];
    for(int i=0;i<=18;i++)if(t&(1<<i))x=fa[x][i];
    for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}
    if(x==y)return x;return fa[x][0];
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1);scanf("%d",&Q);
	while(Q--){
		CL(near);CL(val);CL(ans);
		scanf("%d",&m);top=0;mxh=m;
		for(i=1;i<=m;i++){
			scanf("%d",&a[i]);
			tmp[i]=a[i];ans[a[i]]=0;
			near[a[i]]=mp(0,a[i]);//最近点的距离和标号 
			tree[i]=a[i];//虚树上的点 
		}
		sort(a+1,a+m+1,cmp);
		for(i=1;i<=m;i++){
			int x=a[i];
			if(!top)fa[x]=0;else{//构建虚树 
			for(y=lca(x,st[top]),fa[x]=y;high[st[top]]>high[y];top--)
if(high[st[top-1]]<=high[y])fa[st[top]]=y;
				if(st[top]!=y){
					fa[y]=st[top];//虚树上的父子关系 
					st[++top]=y;near[y]=mp(inf,0);tree[++mxh]=y; 
				}
			}
			st[++top]=x;
		}
		sort(tree+1,tree+mxh+1,cmp);
		for(i=1;i<=mxh;i++){
			x=tree[i];val[x]=size[x];
			if(i>1)in[x]=high[x]-high[fa[x]];//虚树内路径长度 
		}
		for(i=mxh;i>1;i--){//两遍DFS找虚树上每个点属于那个点 
			x=tree[i],y=fa[x];
			near[y]=min(near[y],mp(near[x].X+in[x],near[x].Y));
		}
		for(i=2;i<=mxh;i++){
			x=tree[i],y=fa[x];
			near[x]=min(near[x],mp(near[y].X+in[x],near[y].Y));
		}
		for(i=1;i<=mxh;i++){
			int x=tree[i],y=fa[x],sum=size[find(x,high[y]+1)]-size[x];//路径长度 
			if(!y)ans[near[x].Y]+=n-size[x];else{//父亲不存在则子树以外的点都离该点最近 
				val[y]-=sum+size[x];//虚树中某点为结点的子树中，除去也在虚树中的子节点与其构成的链的点数，剩余的节点数 
				if(near[x].Y==near[y].Y)ans[near[x].Y]+=sum;else{//两边属于同一点 
					int dis=(high[x]-high[y]+near[y].X-near[x].X)/2,z;
					if(dis+near[x].X==high[x]-high[y]-dis+near[y].X&&near[y].Y<near[x].Y)dis--;
					z=find(x,high[x]-dis);//分配答案 
					ans[near[x].Y]+=size[z]-size[x];
					ans[near[y].Y]+=sum-size[z]+size[x];
				}
			}
		}
		for(i=1;i<=mxh;i++)ans[near[tree[i]].Y]+=val[tree[i]];
		for(i=1;i<=m;i++)printf("%d ",ans[tmp[i]]);puts("");
	}
}

BZOJ3879 后缀树+虚树

#include<bits/stdc++.h>
#define N 1001000
#define CL(a) memset(a,0,sizeof(a))
using namespace std;bool v[N];char s[N];long long A;
int n,m,i,j,k,x,y,t,p,q,id,np,nq,cnt,tot,st[N],pos[N],to[N],c[N][26],F[N],fir[N],ne[N],la[N],h[N],f[N][20],dfn[N],Q[N],a[N],sz[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void add(int x){
	for(p=np,st[np=++cnt]=st[p]+1;p&&!c[p][x];p=F[p])c[p][x]=np;to[np]=i;pos[i]=np;
	if(!p)F[np]=1;else if(st[p]+1==st[q=c[p][x]])F[np]=q;else for(st[nq=++cnt]=st[p]+1,memcpy(c[nq],c[q],sizeof c[q]),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}
void dfs(int x){
	for(int i=1;i<=19;i++)f[x][i]=f[f[x][i-1]][i-1];dfn[x]=++id;
	for(int i=fir[x],y;i;i=ne[i])f[y=la[i]][0]=x,h[y]=h[x]+1,dfs(y);
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<=19;i++)if(t>>i&1)x=f[x][i];
    for(i=19;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return x==y?x:f[x][0];
}
void dp(int x){
	sz[x]=v[x]?1:0;
	for(int i=fir[x];i;i=ne[i])dp(la[i]),A=(A+sz[x]*sz[la[i]]*st[x])%23333333333333333,sz[x]+=sz[la[i]];
	fir[x]=0;
}
int main(){
	for(scanf("%d%d%s",&n,&m,s+1),np=cnt=1,i=n;i;i--)add(s[i]-'a');
	for(v[1]=i=1;i<=cnt;i++)if(to[i])for(j=i;!v[j];j=F[j])v[j]=1,ins(F[j],j);
	for(dfs(1),CL(fir),CL(v);m--;printf("%lld\n",A)){
		for(scanf("%d",&k),i=1;i<=k;i++)scanf("%d",&x),a[i]=pos[x],v[a[i]]=1;
		for(sort(a+1,a+k+1,cmp),A=tot=0,Q[t=1]=1,i=1;i<=k;i++){
            for(y=lca(x=a[i],Q[t]);h[y]<h[Q[t]];ins(Q[t-1],Q[t]),t--)if(h[y]>=h[Q[t-1]]){ins(y,Q[t--]);if(Q[t]!=y)Q[++t]=y;break;}
            if(Q[t]!=x)Q[++t]=x;
        }
		for(;--t;ins(Q[t],Q[t+1]));
		for(dp(1),i=1;i<=k;i++)v[a[i]]=0;
	}
}

待做：BZOJ3460

• 相关文章推荐
• 全局相关文章