40分求助(奖励一关注)
查看原帖
40分求助(奖励一关注)
380406
allqpsi楼主2023/7/11 09:05
#include<bits/stdc++.h>
using namespace std;
vector<int>vi[70000];
vector<int>vi2[70000];
vector<int>vi3[70000];
int fa[70000][17],n,a,dep[70000],f[70000],p,ff[70000];
bool vis[70000],viss[70000];
queue<int>qi;
void dfs(int x){
	for(int i=1;i<=16;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=0;i<vi[x].size();i++){
		int v=vi[x][i];
		if(vis[v]){
			continue;
		}
		vis[v]=true;
		fa[v][0]=x;
		dep[v]=dep[x]+1;
		dfs(v); 
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	int k=dep[x]-dep[y];
	for(int i=0;i<=16;i++){
		if(k&(1<<i)){
			x=fa[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=16;i>=0;i--){
		if(fa[x][i]==fa[y][i]){
			continue;
		}
		x=fa[x][i];
		y=fa[y][i];
	}
	return fa[x][0];
}
void dfss(int x){
	int o=0;
	for(int i=0;i<vi3[x].size();i++){
		int v=vi3[x][i];
		dfss(v);
		o+=f[v];
	}
	f[x]+=o;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		bool isit=false;
		while(cin>>a){
			if(a==0){
				break;
			}
			vi[a].push_back(i);
			vi2[i].push_back(a);
			isit=true;
		}
		if(!isit){
			vi2[i].push_back(0);
			vi[0].push_back(i);
			qi.push(i);
		}
	}
	dep[0]=0;
	dfs(0);
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){
		ff[i]=vi2[i].size();
	}
	while(!qi.empty()){
		int i=qi.front();
		qi.pop();
		for(int j=0;j<vi[i].size();j++){
			ff[vi[i][j]]--;
			if(ff[vi[i][j]]==0){
				qi.push(vi[i][j]);
			}
		}
		if(vi2[i].size()==0){
			continue;
		}
		int k=vi2[i][0];
		for(int j=1;j<vi2[i].size();j++){
			k=lca(k,vi2[i][j]);
		}
		f[k]++;
		vi3[k].push_back(i);
	}
	memset(vis,false,sizeof(vis));
	dfss(0);
	for(int i=1;i<=n;i++){
		cout<<f[i]<<endl;
	}
}

2023/7/11 09:05
加载中...