30pts求助
查看原帖
30pts求助
704234
Sad_Rex楼主2023/7/28 09:00
#include<bits/stdc++.h>
//#pragma GCC optimize(3, "Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
using namespace std;
//#define int long long
#define kg putchar(' ')
#define endl puts("")
inline int read(){
    int vis=1,ans=0;
    char x=getchar();
    while(x<'0'||x>'9'){
        if(x=='-')vis=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9'){
        ans=ans*10+x-'0';
        x=getchar();
    }
    return vis*ans;
}
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
const int N=65534;
struct edge{
	int nxt,to;
}e[4*N];
int head[N],Cnt;
inline void addedge(int u,int v){
	++Cnt;
	e[Cnt].to=v;
	e[Cnt].nxt=head[u];
	head[u]=Cnt;
}
struct edgeans{
	int nxt,to;
}ea[4*N];
int Head[N],Ans;
inline void addans(int x,int y){
	++Ans;
	ea[Ans].to=y;
	ea[Ans].nxt=Head[x];
	Head[x]=Ans;
}
int n;
queue<int>q;
int Fajump[N][19];
int Do[N],Dep[N],Size[N];
int Edge[N];
inline int LCA(int x,int y){
	if(x==y)return x;
	if(Dep[x]<Dep[y])swap(x,y);
	for(int i=18;i>=0;i--)if(Dep[Fajump[x][i]]>=Dep[y])x=Fajump[x][i];
	for(int i=18;i>=0;i--)if(Fajump[x][i]!=Fajump[y][i])x=Fajump[x][i],y=Fajump[y][i];
	return Fajump[x][0];
}
inline void Getsize(int Fa){
	Size[Fa]=1;
	for(int i=Head[Fa];i;i=ea[i].nxt){
		int Son=ea[i].to;
		Getsize(Son);
		Size[Fa]+=Size[Son];
	}
}
signed main(){
	n=read();
	memset(Do,-1,sizeof(Do));
	for(int i=1;i<=n;i++){
		int x,Tmp=0;
		while(1){
			x=read();
			if(!x)break;
			++Tmp;
			addedge(x,i);
		}
		if(!Tmp)q.push(i),Do[i]=0;
		Edge[i]=Tmp;
	}
	while(!q.empty()){
		int Top=q.front();
		q.pop();
		addans(Do[Top],Top);
		Fajump[Top][0]=Do[Top],Dep[Top]=Dep[Do[Top]]+1;
		for(int i=1;i<=18;i++){
			Fajump[Top][i]=Fajump[Fajump[Top][i-1]][i-1];
		}
		for(int i=head[Top];i;i=e[i].nxt){
			int Son=e[i].to;
			if(Do[Son]==-1)Do[Son]=Top;
			else Do[Son]=LCA(Do[Son],Top);
			if(--Edge[Son]==0)q.push(Son);
		}
	}
	Getsize(0);
	for(int i=1;i<=n;i++)print(Size[i]-1),endl;
    return 0;
}

@ran_qwq

2023/7/28 09:00
加载中...