20分求调,玄关
查看原帖
20分求调,玄关
1070754
lijunxi20231818楼主2024/3/27 21:18
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int n, in[maxn], lca[maxn], fa[maxn][20], pow2[20], ans[maxn], dep[maxn];
vector<int> e[maxn], t[maxn];
void add_edge(int u, int v){
	t[u].push_back(v);
	fa[v][0] = u;
	dep[v] = dep[u] + 1;
	for(int i = 1; i <= 20; i++){
		fa[v][i] = fa[fa[v][i - 1]][i - 1];
	}
}
int LCA(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = 20; i >= 0; i--){
		if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	}
	if(u == v) return u;
	for(int i = 20; i >= 0; i--){
		if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}
void toposort(){
	queue<int> q;
	q.push(n + 1);
	add_edge(0, n + 1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0; i < e[u].size(); i++){
			int v = e[u][i];
			in[v]--;
			if(lca[v] == v) 
				lca[v] = u;
			else 
				lca[v] = LCA(lca[v], u);
			if(!in[v]) 
				q.push(v), add_edge(lca[v], v);
		}
	}
}
bool vis[maxn];
void dfs(int x){
	vis[x] = 1; ans[x] = 1;
	for(int i = 0; i < t[x].size(); i++){
		if(!vis[t[x][i]]){
			dfs(t[x][i]);
			ans[x] += ans[t[x][i]];
		}
	}
}
//void init_pow2(){
//	pow2[0] = 1;
//	for(int i = 1; i <= 20; i++) pow2[i] = 2 * pow2[i - 1];
//}
signed main(){
	freopen("1.in", "r", stdin);
	freopen("11.out", "w", stdout);
//	init_pow2();
	cin >> n;
	for(int v = 1; v <= n; v++){
		int u;
		cin >> u;
		while(u){
			e[u].push_back(v);
			in[v]++;
			cin >> u;
		}
	}
	for(int i = 1; i <= n; i++){
		lca[i] = i;
		if(!in[i]) 
			e[n + 1].push_back(i), in[i]++;
	}
	lca[n + 1] = n + 1;
	toposort();
	dfs(n + 1);
	for(int i = 1; i <= n; i++){
		cout << ans[i] - 1 << endl;
	}
	return 0;
}
2024/3/27 21:18
加载中...