题解 P3233 【[HNOI2014]世界树】

题意:标记一些树上的点,每个点会被最近(编号最小)的标记点控制,问每个标记点会控制多少点 根据套路先搞出虚树,然后考虑怎么$DP$ 首先两遍$dfs$求出虚树上每个点被那个点控制 第一遍是$dfs$求最近的儿子,第二遍是考虑每个点父亲对其他儿子的贡献 所以第一遍要先$dfs$儿子,第二遍要后$dfs$儿子 然后对于虚树上每一条边 ①:两端点被同一个点控制,直接把这两个端点所属的点的贡献加上这两个点不在虚树中的儿子的$sz$ ②:两端点被不同点控制,那么中间一定有一个分界点,使得分界点上面的点的$sz$属于上端点,下面属于下端点 这个分界点可以通过倍增求得,注意计算答案要把两端点的贡献去掉(开区间) 考虑怎么计算每个点$u$不在虚树中的儿子的$sz$,记他是$sur[u](Surplus)$,一开始等于$sz[u]$ 对于虚树上$(u,v)$这条边,倍增求出$(u,v)$上原树中离$u$最近的点$s$ $sur[u]$减去所有的这样的$sz[s]$就是点$u$不在虚树中的儿子的$sz$ $dp$完后每个点所属的点加上再这个点的剩余量就是答案了 ``` #include<bits/stdc++.h> #define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i) #define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to) #define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; char ss[1<<17],*A=ss,*B=ss; inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;} template<class T>inline void sd(T&x){ char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48; while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y; } char sr[1<<21],z[20];int C=-1,Z; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} template<class T>inline void we(T x){ if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]=' '; } const int N=3e5+5,M=19,inf=1e9; typedef int arr[N]; struct eg{int nx,to;}e[N<<1]; int n,m,k,ce,dft,fa[N][M];arr a,b,bl,fi,fg,sz,son,top,dep,Log,dfn,sur,ans,S; void dfs(int u){ dep[u]=dep[fa[u][0]]+(sz[u]=1);dfn[u]=++dft; for(int i=0;fa[u][i];++i)fa[u][i+1]=fa[fa[u][i]][i]; go(u)if(v^fa[u][0]){ fa[v][0]=u,dfs(v),sz[u]+=sz[v]; if(sz[v]>sz[son[u]])son[u]=v; } } void dfs(int u,int t){ top[u]=t;if(son[u])dfs(son[u],t); go(u)if(v^fa[u][0]&&v^son[u])dfs(v,v); } inline int lca(int u,int v){ for(;top[u]^top[v];dep[top[u]]>dep[top[v]]?u=fa[top[u]][0]:v=fa[top[v]][0]); return dep[u]<dep[v]?u:v; } inline int dis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];} inline void add(int u,int v){e[++ce]={fi[u],v},fi[u]=ce;} void dfs1(int u){int d1,d2; bl[u]=fg[u]?u:0;sur[u]=sz[u]; go(u){ dfs1(v); d1=dep[bl[v]]-dep[u],d2=bl[u]?dep[bl[u]]-dep[u]:inf; if(d1<d2||(d1==d2&&bl[v]<bl[u]))bl[u]=bl[v]; } } void dfs2(int u){int d1,d2; go(u){ d1=dis(bl[u],v),d2=dis(bl[v],v); if(d1<d2||(d1==d2&&bl[u]<bl[v]))bl[v]=bl[u]; dfs2(v); } } void dp(int u){int s,mid,nt,d1,d2; go(u){ dp(v);s=mid=v; fd(i,Log[dep[v]],0)if(dep[fa[s][i]]>dep[u])s=fa[s][i]; sur[u]-=sz[s]; if(bl[u]==bl[v]){ans[bl[u]]+=sz[s]-sz[v];continue;}; fd(i,Log[dep[v]],0){ nt=fa[mid][i];if(dep[nt]<=dep[u])continue; d1=dis(nt,bl[v]),d2=dis(nt,bl[u]); if(d1<d2||(d1==d2&&bl[v]<bl[u]))mid=nt; } ans[bl[u]]+=sz[s]-sz[mid]; ans[bl[v]]+=sz[mid]-sz[v]; }ans[bl[u]]+=sur[u];fi[u]=0; } inline bool cmp(const int&a,const int&b){return dfn[a]<dfn[b];} inline void sol(){ sd(k);fp(i,1,k)sd(a[i]),b[i]=a[i],fg[a[i]]=1; sort(a+1,a+k+1,cmp);static int top=1;S[1]=1;ce=0; fp(i,1,k){ int x=a[i],p=lca(S[top],x); while(dep[p]<dep[S[top]]){ if(dep[p]>=dep[S[top-1]]){ add(p,S[top--]); if(S[top]^p)S[++top]=p; break; }add(S[top-1],S[top]),--top; }if(S[top]^x)S[++top]=x; }while(top>1)add(S[top-1],S[top]),--top; dfs1(1),dfs2(1);dp(1); fp(i,1,k)we(ans[b[i]]),fg[b[i]]=ans[b[i]]=0;sr[++C]='\n'; } int main(){ #ifndef ONLINE_JUDGE file("s"); #endif sd(n);int u,v;fp(i,2,n)Log[i]=Log[i>>1]+1; fp(i,2,n)sd(u),sd(v),add(u,v),add(v,u); dfs(1),dfs(1,1);sd(m); memset(fi,0,sizeof fi);while(m--)sol(); return Ot(),0; } ```