#2815. [ZJOI2012]灾难

因为是一个有向无环图,一个生物灭绝的条件是它的食物都灭绝.

那么我们考虑按$topotopo$序重构这张图,因为一定是一个森林/树,我们考虑增加一个超级源点$uu$.然后且当它的祖先节点灭绝它就会灭绝,考虑把它**到它所有食物的$lcalca$下面,然后灭绝它的毁灭值就是$\mathrm{子}\mathrm{树}\mathrm{大}\mathrm{小}-1子树大小-1$啦.

树的$lcalca$的倍增和$rmqrmq$的倍增是有一定的区别的,$rmqrmq$包含自己,而树不包含自己节点.

$code:code:$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const int M=17;
const int mod=998244353;

vector<int>g[N],G[N];
int d[N],n,dep[N];
int sx[N],id=0;
int f[N][M];
int ans[N];

void dfs(int u)
{
	ans[u]=1;
	for(int v:G[u])
	{
		dfs(v);
		ans[u]+=ans[v];
	}
}


int LCA(int u,int v)
{
	if(dep[u]<dep[v])	swap(u,v);
	for(int i=16;i>=0;i--)
	{
		if(dep[f[u][i]]>=dep[v])	u=f[u][i];
	}
	if(u==v)	return u;
	for(int i=16;i>=0;i--)
	{
		if(f[u][i]!=f[v][i])	u=f[u][i],v=f[v][i];
	}
	return f[u][0];
}

void pre(int u)
{
	for(int i=1;i<=16;i++)
	{
		f[u][i]=f[f[u][i-1]][i-1];
	}
}

void topo()
{
	queue<int>Q;
	for(int i=1;i<=n;i++)
		if(!d[i])	Q.push(i),sx[++id]=i;
	while((int)Q.size())
	{
		int x=Q.front();
		Q.pop();
		for(int u:g[x])
		{
			d[u]--;
			if(d[u]==0)	sx[++id]=u,Q.push(u);
		}
	}
	dep[n+1]=1;
	for(int i=id;i>=1;i--)
	{
		if((int)g[sx[i]].size()==0)
		{
			f[sx[i]][0]=n+1;
			dep[sx[i]]=2;
			G[n+1].push_back(sx[i]);
			continue;
		}
		int lca=g[sx[i]][0];
		for(int u:g[sx[i]])
		{
			lca=LCA(lca,u);
		}
		G[lca].push_back(sx[i]);
		dep[sx[i]]=dep[lca]+1;
		f[sx[i]][0]=lca;
		pre(sx[i]);
	}
}

void run()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		while(true)
		{
			scanf("%d",&x);
			if(x==0)	break;
			g[i].push_back(x);
			d[x]++;
		}
	}
	topo();
	dfs(n+1);
	for(int i=1;i<=n;i++)
		ans[i]--,printf("%d\n",ans[i]);
}

int main()
{
	int T=1;
	//scanf("%d",&T);
	while(T--)	run();
	return 0;
}