【洛谷 P2597】 [ZJOI2012]灾难（LCA）

题目链接

考虑建一棵树，使一个生物灭绝时他的子树都会灭绝，显然这样答案就是以每个点为根的子树大小-1.

为什么原图不是一棵树，因为一个生物可能会以多个生物为食，所以按拓扑序来建树，把每个遍历到的点的父亲设为它的所有食物的\(LCA\)。

因为是按拓扑序来的，所以当遍历到这个生物时，它的所有食物肯定是已经在树中的。

#include <cstdio>

#include <queue>

#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);

using namespace std;

const int MAXN = 100010;

struct Edge{

	int next, to;

};

struct edge{

	Edge e[MAXN << 4];

	int head[MAXN], num;

	inline void Add(int from, int to){

		e[++num] = (Edge){ head[from], to }; head[from] = num;

	}

}S, T, P;

int n, in[MAXN], IN[MAXN], dep[MAXN], size[MAXN], f[MAXN][20], a;

queue <int> q;

inline int LCA(int u, int v){

	if(dep[u] > dep[v]) swap(u, v);

	int cha = dep[v] - dep[u];

	if(cha)

		for(int i = 0; i <= 19; ++i)

			if((cha >> i) & 1)

				v = f[v][i];

	if(u == v) return u;

	for(int i = 19; ~i; --i)

		if(f[u][i] != f[v][i])

			u = f[u][i], v = f[v][i];

	return f[u][0];

}

int main(){

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i)

		while(scanf("%d", &a) && a) S.Add(a, i), ++in[i], T.Add(i, a);

	for(int i = 1; i <= n; ++i) if(!in[i]) q.push(i);

	while(q.size()){

		int now = q.front(); q.pop();

		int p = T.e[T.head[now]].to;

		for(int i = T.e[T.head[now]].next; i; i = T.e[i].next)

			p = LCA(p, T.e[i].to);

		P.Add(now, p); f[now][0] = p; dep[now] = dep[p] + 1; ++IN[p];

		for(int i = 1; i <= 17; ++i)

			f[now][i] = f[f[now][i - 1]][i - 1];

		for(int i = S.head[now]; i; i = S.e[i].next)

			if(!(--in[S.e[i].to]))

				q.push(S.e[i].to);

	}

	for(int i = 1; i <= n; ++i)

		if(!IN[i])

			q.push(i);

	while(q.size()){

		int now = q.front(); q.pop();

		for(int i = P.head[now]; i; i = P.e[i].next){

			size[P.e[i].to] += size[now] + 1;

			if(!(--IN[P.e[i].to]))

				q.push(P.e[i].to);

		}

	}

	for(int i = 1; i <= n; ++i)

		printf("%d\n", size[i]);

	return 0;

}