80pts求调
查看原帖
80pts求调
538427
czy0323楼主2023/8/1 12:31
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5+5;
int n;
vector<int> g[N], g1[N], tr[N];
int out[N], siz[N], dep[N];
int st[N][20];
queue<int> q;

inline int getlca(int a, int b){
	if( dep[a] < dep[b] )
		swap(a, b);
	for(int i = 19; i >= 0; i--)
		if( dep[st[a][i]] >= dep[b] )
			a = st[a][i];
	if( a == b )	return a;
	for(int i = 19; i >= 0; i--)
		if( st[a][i] != st[b][i] )
			a = st[a][i], b = st[b][i];
	return st[a][0];
}

inline void dfs(int now){
	siz[now] = 1;
	for(auto i : tr[now]){
		dfs(i);
		siz[now] += siz[i];
	}
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		int v;
		while( true ){
			cin >> v;
			if( !v )	break;
			g[v].push_back(i);
			g1[i].push_back(v);
			out[i]++;
		}
	}
	for(int i = 1; i <= n; i++)
		if( !out[i] ){
			q.push(i);
			tr[0].push_back(i);
		}
	while( !q.empty() ){
		int h = q.front();
		q.pop();
		for(auto i : g[h]){
			out[i]--;
			if( !out[i] ){
				int lca = g1[i][0];
				for(int j = 1; j < g1[i].size(); j++)
					lca = getlca(lca, g1[i][j]);
				st[i][0] = lca, dep[i] = dep[lca] + 1;
				for(int j = 1; j <= 19; j++)
					st[i][j] = st[st[i][j - 1]][j - 1];
				tr[lca].push_back(i);
				q.push(i);
			}
		}
	}
	dfs(0);
	for(int i = 1; i <= n; i++)
		cout << siz[i] - 1 << "\n";
	return 0;
}
2023/8/1 12:31
加载中...