记录编号	590980	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 灾难	最终得分	100
用户昵称	袁书杰	是否通过	通过
代码语言	C++	运行时间	0.677 s
提交时间	2024-07-14 18:55:32	内存使用	9.93 MiB

#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct edge {
	int u,v,nxt;
} e[65534*2],e1[65534*2];
int etot,head[65534*2],etot1,head1[65534*2],deep[65534*2],ancester[65534*2][55],in[65534*2],dad[65534*2],size[65534*2];
void adde(int u,int v) {
	e[++etot]= {u,v,head[u]};
	head[u]=etot;
}
void adde1(int u,int v) {
	e1[++etot1]= {u,v,head1[u]};
	head1[u]=etot1;
}
int lca(int x,int y) {
    if(x==y){
        return x;
    }
	if(deep[x]<deep[y]) {
		swap(x,y);
	}
	for(int i=18; i>=0; i--) {
		if(deep[ancester[x][i]]>=deep[y]) {
			x=ancester[x][i];
		}
	}
	if(x==y) {
		return x;
	}
	for(int i=18; i>=0; i--) {
	    if(ancester[x][i]!=ancester[y][i]){
	        x=ancester[x][i];
	        y=ancester[y][i];
        }
	}
	return ancester[x][0];
}
void dfs(int u) {
    size[u]=1;
	for (long long i = head1[u]; i; i = e1[i].nxt) {
		long long v = e1[i].v;
		dfs(v);
		size[u]+=size[v];
	}
}
void toposort() {
	queue<int> S;
	for (int i = 1; i <= n; i++)
		if (in[i] == 0) S.push(i),dad[i]=0;
	while (!S.empty()) {
		int u = S.front();
		S.pop();
		adde1(dad[u],u);
		ancester[u][0]=dad[u];
		deep[u]=deep[dad[u]]+1;
		for(int i=1; i<=18; i++) {
			ancester[u][i]=ancester[ancester[u][i-1]][i-1];
		}
		for (long long j = head[u]; j; j = e[j].nxt) {
			long long v = e[j].v;
			if(dad[v]==-1) {
				dad[v]=u;
			} else {
				dad[v]=lca(dad[v],u);
			}
			if(--in[v]==0){
			    S.push(v);
            }
		}
	}
}
int main() {
	freopen("catas.in","r",stdin);
	freopen("catas.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	for(int i=1; i<=65534*2-2; i++) {
		dad[i]=-1;
	}
	cin>>n;
	for(int i=1; i<=n; i++) {
		int x;
		while(cin>>x,x!=0) {
			adde(x,i);
			in[i]++;
		}
	}
	toposort();
	dfs(0);
	for(int i=1; i<=n; i++) {
	    cout<<size[i]-1<<endl;
	}
	return 0;
}