30分求条,玄关
查看原帖
30分求条,玄关
672534
Field_Mouse楼主2024/3/16 17:10
#include<bits/stdc++.h>
#define AC return 0;
#define pr(n) printf("%d",(n))
#define hh puts("")
#define kg printf(" ")
using namespace std;
namespace fr{
	int read()
	{
		int x=0,flag=1;
		char ch=getchar();
		for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')flag=-1;
		for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
		return flag*x;
	}
}
using namespace fr;
const int N = 1<<16;
int n;
vector<int> g1[N<<1],g2[N<<1];
int in[N],f[N][21],sz[N],dep[N];
int d[N];
void dfs(int x)
{
	sz[x]=1;
	for(auto i:g2[x])
	{
		dfs(i);
		sz[x]+=sz[i];
	}
}
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[f[x][i]]>=dep[y])x=f[x][i];
	for(int i=18;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
queue<int> q;
int main()
{
	n=read();
	for(int i=1;i<N;i++)d[i]=-1;
	for(int i=1;i<=n;i++)
	{
		int x=read();
		while(x)
		{
			g1[x].push_back(i);
			in[i]++;
			x=read();
		}
	}
	
	for(int i=1;i<=n;i++)
	{
//		cout<<in[i]<<endl;
		if(!in[i])
		{
			q.push(i);
			d[i]=0;
		}
	}
	while(q.size()){
		int now=q.front();
		q.pop();
		g2[d[now]].push_back(now);
		f[now][0]=d[now];
		dep[now]=dep[d[now]]+1;
		for(int i=1;i<=18;i++)f[now][i]=f[f[now][i-1]][i-1];
		for(auto i:g1[now])
		{
			if(d[i]==-1)d[i]=now;
			else d[i]=lca(d[i],now);
			--in[i];
			if(!in[i])q.push(i);
		}
	}
	dfs(0);
	for(int i=1;i<=n;i++)pr(sz[i]-1),hh;
	AC
}
2024/3/16 17:10
加载中...