题解 P3233 【[HNOI2014]世界树】
Published:
本题要建虚树是显然的，建虚树复杂度是 $O(n)$ (因为 $n$ 和 $\sum m$ 同级，所以以下全部用 $n$ 代替)。考虑我们建完虚树之后如何 $dp$ 。至于不会如何建虚树的，建议做一下这题 [SDOI2011]消耗战
首先求出每个虚树上的点被哪些点控制，这里我们使用两次 $dfs$ ，一次求子树(虚树子树)内的贡献，此次为自下而上更新，第二次求子树外对自己的贡献，此次为自上而下更新。这两步操作是 $o(n)$的。
处理完了虚树上的点，接下来考虑虚树边上的点(包括虚边在实树里对于一段路径及其分支构成的树)的贡献：当虚边两端点被相同的关键点控制，即虚边全部归同一个关键点控制，倍增到上端点下端的第一个实点求这一段构成的树上的节点数；当虚边两端点被不同的关键点控制，那必然存在一个分界点，分界点上端归上端点的控制点控制，下端归下端点的控制点控制，这里通过倍增找分界点。这一步复杂度是 $O(nlogn)$ 。
最后，就是那些即不在边上也不在虚树上的点。我们考虑这些点在哪些虚树上点的子树中(建虚树的时候加入 $1$ 号节点，保证所有节点都被存在于虚树上一个节点的子树中)，对于虚树上一个点，我们把它子树中存在于虚树中的节点(或虚边上的点)全部减去，剩下的就是那些最终需要统计的贡献。这一步的时间复杂度 $O(nlogn)$ 。
总时间复杂度 $O(nlogn)$ 。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define REP(i,u) for(re int i=hd[u],v=ed[i].to;i;i=ed[i].nx,v=ed[i].to)
//#define gc getchar()
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),ft==fs))?0:*fs++
#define fs first
#define sc second
using namespace std;
char *fs,*ft,buf[1<<18];
const int N=3e5+10,inf=1e9+7;
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
struct ao{
int nx,to;
}ed[N];
struct in{
int w,id;
}a[N];
vector<int>tr[N];
int n,q,m,fl,id;
int ans[N],as[N];
int dfn[N],vis[N],siz[N],hd[N],fa[N][21],dep[N],s[N],tp;
V add(int u,int v){ ed[++fl]=(ao){hd[u],v},hd[u]=fl;}
V dfs1(int u){
dfn[u]=++id,siz[u]=1;
int z=tr[u].size(),v=0;
FOR(i,0,z-1){
v=tr[u][i];
if(v==fa[u][0]) continue;
fa[v][0]=u,dep[v]=dep[u]+1;
dfs1(v),siz[u]+=siz[v];
}
return ;
}
I lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
ROF(k,18,0) if(dep[fa[x][k]]>=dep[y]&&fa[x][k]) x=fa[x][k];
if(x==y) return x;
ROF(k,18,0) if(fa[x][k]!=fa[y][k]&&fa[x][k]) x=fa[x][k],y=fa[y][k];
return fa[x][0];
}
typedef pair<int,int> PI;
PI f[N];
int ff[N],sz[N];
V dfs2(int u){
if(vis[u]) f[u]=make_pair(0,u);
PI tmp;
REP(i,u) dfs2(v),tmp=f[v],tmp.fs+=dep[v]-dep[u],f[u]=min(f[u],tmp);
return ;
}
V dfs3(int u,int dis,int p){
if(make_pair(dis,p)<f[u]) f[u]=make_pair(dis,p);
else dis=f[u].fs,p=f[u].sc;
REP(i,u) dfs3(v,dis+dep[v]-dep[u],p);
}
I get(int u){
int x=u;
ROF(k,18,0) if(dep[fa[x][k]]>dep[ff[u]]&&fa[x][k]) x=fa[x][k];
return x;
}
V dfs4(int u){
int x=u;
REP(i,u) dfs4(v);
if(fl&&ff[u]) x=get(u),sz[ff[u]]+=siz[x];
return ;
}
V dfs5(int u){
ans[f[u].sc]+=siz[u]-sz[u];
REP(i,u) dfs5(v);
}
V dfs6(int u){
int x,y;
PI tmp1,tmp2;
REP(i,u){
if(f[u]==f[v]) x=get(v),ans[f[u].sc]+=siz[x]-siz[v];
else{
x=v;
ROF(k,18,0){
if(dep[fa[x][k]]<dep[u]||!fa[x][k]) continue;
tmp1=f[v],tmp1.fs+=dep[v]-dep[fa[x][k]];
tmp2=f[u],tmp2.fs+=dep[fa[x][k]]-dep[u];
if(tmp1<tmp2) x=fa[x][k];
}
y=get(v);
ans[f[u].sc]+=siz[y]-siz[x];
ans[f[v].sc]+=siz[x]-siz[v];
}
dfs6(v);
}
return ;
}
B cmp(in x,in y){ return dfn[x.w]<dfn[y.w];}
int sck[N],cnt;
int main(){
int x,y;
n=read();
FOR(i,2,n) x=read(),y=read(),\
tr[x].push_back(y),\
tr[y].push_back(x);
dfs1(1);
FOR(k,1,18) FOR(i,1,n) fa[i][k]=fa[fa[i][k-1]][k-1];
q=read();
FOR(i,1,n) f[i]=make_pair(inf,inf);
FOR(i,1,q){
m=read();
FOR(j,1,m) a[j].w=read(),vis[a[j].w]=1,a[j].id=j;
sort(a+1,a+1+m,cmp);
s[tp=1]=1,sck[cnt=1]=1,fl=0;
FOR(j,1,m){
int x=a[j].w,y=lca(x,s[tp]);
if(x==1) continue;
sck[++cnt]=x,sck[++cnt]=y;
while(tp>1&&dep[s[tp-1]]>=dep[y])
add(s[tp-1],s[tp]),ff[s[tp]]=s[tp-1],--tp;
if(s[tp]!=y) add(y,s[tp]),ff[s[tp]]=y,s[tp]=y;
s[++tp]=x;
}
while(tp>1) add(s[tp-1],s[tp]),ff[s[tp]]=s[tp-1],--tp;
dfs2(1);
dfs3(1,f[1].fs,f[1].sc);
dfs4(1);
dfs5(1);
dfs6(1);
FOR(j,1,m) as[a[j].id]=ans[a[j].w];
FOR(j,1,m) printf("%d ",as[j]);
printf("\n");
FOR(j,1,cnt) vis[sck[j]]=hd[sck[j]]=0,\
sz[sck[j]]=ans[sck[j]]=ff[sck[j]]=0,\
f[sck[j]]=make_pair(inf,inf);
sz[0]=0;
}
return 0;
}
}