记录编号	576405	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2012] 灾难	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.916 s
提交时间	2022-10-08 18:30:04	内存使用	23.37 MiB

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n, inc[MAXN], fa[MAXN], dep[MAXN], f[30][MAXN], size[MAXN];
vector<int> cd[MAXN], g[MAXN];
int lca(int x, int y) {
	if(x == y) {
		return x;
	}
	if(dep[x] < dep[y]) {
		swap(x, y);
	}
	for(int i = 20; i >= 0; i --) {
		int u = f[i][x];
		if(dep[u] >= dep[y]) {
			x = u;
		}
	}
	if(x == y) {
		return x;
	}
	for(int i = 20; i >= 0; i --) {
		int u = f[i][x], v = f[i][y];
		if(u != v) {
			x = u;
			y = v;
		}
	}
	return f[0][x];
	
}
void dfs(int x) {
	size[x] = 1;
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		dfs(u);
		size[x] += size[u];
	}
}
int main() {
	freopen("catas.in", "r", stdin);
	freopen("catas.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		int x;
		while(cin >> x) {
			if(x == 0) {
				break;
			}
			g[x].push_back(i);
			inc[i] ++;
		}
	}
	memset(fa, -0x3f, sizeof(fa));
	queue<int> q;
	for(int i = 1; i <= n; i ++) {
		if(!inc[i]) {
			fa[i] = 0;
			q.push(i);
		}
	}
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		cd[fa[x]].push_back(x);
		f[0][x] = fa[x];
		dep[x] = dep[fa[x]] + 1;
		for(int i = 1; i <= 20; i ++) {
			f[i][x] = f[i - 1][f[i - 1][x]];
		}
		for(int i = 0; i < g[x].size(); i ++) {
			int u = g[x][i];
			if(fa[u] < 0) {
				fa[u] = x;
			}
			else {
				fa[u] = lca(fa[u], x);
			}
			if(-- inc[u] == 0) {
				q.push(u);
			}
		}
	}
	dfs(0);
	for(int i = 1; i <= n; i ++) {
		cout << size[i] - 1 << endl;
	}
    return 0;
}