【题解】LuoGu2597：[ZJOI2012]灾难

原题传送门
如果以生产者开始为根建树的话
一个点可以向该点所有食物的$lca$以及这个$lca$的所有祖先贡献1灾难值
根据上面两句话，就可以把这道题给做掉了

不过还是讲一讲具体写法
先拓扑排序调整顺序（从高级消费者到低级生产者），然后从生产者开始建树，一边建一边初始化倍增数组
最终从最高级的消费者开始向下面的东西贡献灾难值

Code：

#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], in[maxn], d[maxn], que[maxn], cnt, fa[maxn][25], size[maxn], n;
queue <int> q;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
} 

void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; }

void topsort(){
	for (int i = 1; i <= n; ++i)
		if (!in[i]) q.push(i);
	while (!q.empty()){
		int u = q.front(); q.pop();
		que[++cnt] = u;
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			if (!(--in[v])) q.push(v);
		}
	}
}

int get(int u, int v){
	if (d[u] > d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i) if (d[u] <= d[fa[v][i]]) v = fa[v][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

int main(){
	n = read();
	for (int i = 1; i <= n; ++i){
		int x = read();
		while (x) ++in[x], addedge(i, x), x = read();
	}
	topsort();
	for (int i = n; i; --i){
		int u = que[i], x = edge[head[u]].to;
		for (int j = edge[head[u]].next; j; j = edge[j].next) x = get(x, edge[j].to);
		fa[u][0] = x, d[u] = d[x] + 1;
		for (int j = 0; fa[u][j]; ++j) fa[u][j + 1] = fa[fa[u][j]][j];
	}
	for (int i = 1; i <= n; ++i) ++size[que[i]], size[fa[que[i]][0]] += size[que[i]];
	for (int i = 1; i <= n; ++i) printf("%d\n", size[i] - 1);
	return 0;
}