luogu2597-[ZJOI2012]灾难 && DAG支配树

Description

P2597 [ZJOI2012]灾难 - 洛谷 | 计算机科学教育新生态

Solution

根据题意建图, 新建一个 (S) 点, 连向每个没有入边的点.

定义每个点 (P) 的支配点为从 (S) 到 (P) 的任意路径必经的点. 那么题意便为对于每一个点, 求有多少个点以它作为支配点.

考虑建立一棵支配树, 其中除了 (S) 之外的点 (P) 的父亲 ( ext{fa} (P)) 表示距离 (P) 最近的支配点. 显然 ( ext{fa} ( ext{fa} (P))) 也为 (P) 的支配点.

我们先对图拓扑排序.

考虑所有能直接到达点 (V) 的点 (U), 即存在边 ((U,V)). 那么 ( ext{fa} (V)) 显然为所有 (U) 在支配树上的 ( ext{lca}). 之后在支配树上加入边 (( ext{fa} (V), V)) 即可. 对于 ( ext{lca}), 可以通过倍增 (O(log n)) 维护.

之后通过在支配树上DP即可求得结果. 同时, 发现支配树和DAG上的拓扑序相同, 可以利用刚才求到的拓扑序直接DP.

时间复杂度 (O((n+m) log n)).

注意必须建立 (S)点, 否则如果多个没有入边的点时会死.==

Code

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;

//---------------------------------------
const int nsz=65600,msz=1.5e6+50;
int n,ans[nsz];
struct te{int t,pr;}edge[msz];
int hd[nsz],pe=1,in[nsz];
void adde(int f,int t){
	edge[++pe]=(te){t,hd[f]};
	hd[f]=pe;
	++in[t];
}
#define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)


int que[nsz],qh=1,qt=0;
int tp[nsz],pt=0;
void gettp(){
//	rep(i,1,n)if(in[i]==0)que[++qt]=i;
	que[++qt]=n+1;
	int u;
	while(qh<=qt){
		u=que[qh++],tp[++pt]=u;
		forg(u,i,v){
			--in[v];
			if(in[v]==0)que[++qt]=v;
		}
	}
}


int fa[nsz][20],fa0[nsz],dep[nsz]{-1};

void addfa(int p,int f){
	dep[p]=dep[f]+1;
	fa[p][0]=f;
	rep(i,1,18)fa[p][i]=fa[fa[p][i-1]][i-1];
}
int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	repdo(i,18,0){
		if(dep[fa[a][i]]<dep[b])continue;
		a=fa[a][i];
	}
	if(a==b)return a;
	repdo(i,18,0){
		if(fa[a][i]==fa[b][i])continue;
		a=fa[a][i],b=fa[b][i];
	}
	return fa[a][0];
}

void sol(){
	rep(i,1,n+1){
		int p=tp[i];
		if(fa0[p])addfa(p,fa0[p]);
		forg(p,j,v){
			if(fa0[v]==0)fa0[v]=p;
			else fa0[v]=lca(fa0[v],p);
		}
	}
	repdo(i,n+1,2){
		int p=tp[i];
		ans[fa[p][0]]+=ans[p]+1;
	}
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	int a;
	rep(i,1,n){
		while(cin>>a,a){
			adde(a,i);
		}
		if(in[i]==0)adde(n+1,i);
	}
	gettp();
	sol();
	rep(i,1,n)cout<<ans[i]<<'
';
	return 0;
}