记录编号	600930	评测结果	AAAAAAAAAA
题目名称	1321.[ZJOI 2012] 灾难	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.762 s
提交时间	2025-05-21 18:58:31	内存使用	14.66 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int N,in[maxn],top[maxn],fa[maxn][20],lg2[maxn]={-1},dep[maxn],size[maxn];
vector<int>G1[maxn],G2[maxn],G3[maxn];
void topsort(){
	int cnt=0;
	queue<int>q;
	for(int i=1;i<=N;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		top[++cnt]=u;
		for(int i=0;i<G2[u].size();i++){
			int v=G2[u][i];
			in[v]--;
			if(!in[v])
				q.push(v);
		}
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	while(dep[u]>dep[v])
		u=fa[u][lg2[dep[u]-dep[v]]];
	if(u==v)return u;
	for(int k=lg2[dep[u]];k>=0;k--)
		if(fa[u][k]!=fa[v][k])
			u=fa[u][k],v=fa[v][k];
	return fa[u][0];
}
void dfs(int u){
	size[u]=1;
	for(int i=0;i<G3[u].size();i++){
		int v=G3[u][i];
		dfs(v);
		size[u]+=size[v];
	}
}
int main(){
	freopen("catas.in", "r", stdin);
		freopen("catas.out", "w" ,stdout);
	ios::sync_with_stdio(false);
	cin>>N;
	for(int i=1;i<=N;i++)
		lg2[i]=lg2[i>>1]+1;
	for(int i=1,x;i<=N;i++)
		while(cin>>x&&x){
			G1[i].push_back(x);
			G2[x].push_back(i);
			in[i]++;
		}
	topsort();
	for(int i=1;i<=N;i++){
		if(!G1[top[i]].size())
			G1[top[i]].push_back(N+1);
		int x=G1[top[i]][0];
		for(int j=1;j<G1[top[i]].size();j++)
			x=LCA(x,G1[top[i]][j]);
		G3[x].push_back(top[i]);
		fa[top[i]][0]=x;
		dep[top[i]]=dep[x]+1;
		for(int k=1;k<=lg2[dep[top[i]]];k++)
			fa[top[i]][k]=fa[fa[top[i]][k-1]][k-1];
	}
	dfs(N+1);
	for(int i=1;i<=N;i++)
		cout<<size[i]-1<<endl;
	return 0;
}