BZOJ2815 [ZJOI2012]灾难

灭绝树的模板题么。之前不知道这题，差点当原创题出出去了。

好像有不少人不知道这东西的样子？orz zhx。

灭绝树只有一句口诀：一个东西的父亲是所有入边的另一端的点的LCA。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct edge {
	int t;
	edge *next;
};

const int maxn = 70009;
const int maxl = 19;
const int maxe = 2000009;

int n, ind[maxn], oud[maxn], tpo[maxn], ath[maxn][maxl], sz[maxn], d[maxn];
edge *ha[maxn], *hr[maxn], *ht[maxn];

inline void addEdge(edge** head, int u, int v) {
	edge* ep = new edge;
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep;
}

int LCA(int u, int v) {
	if (d[u] < d[v])
		swap(u, v);
	for (int i = maxl - 1; i >= 0; -- i)
		if (d[ath[u][i]] >= d[v])
			u = ath[u][i];
	if (u == v)
		return u;
	for (int i = maxl - 1; i >= 0; -- i)
		if (ath[u][i] ^ ath[v][i]) {
			u = ath[u][i];
			v = ath[v][i];
		}
	return ath[u][0];
}

void topSort() {
	static int q[maxn];
	int hd(0), tl(0);
	for (int i = 1; i <= n; ++ i)
		if (!ind[i])
			tpo[tl ++] = i;
	while (hd < tl) {
		int p(tpo[hd ++]);
		for (edge* e = ha[p]; e; e = e-> next) {
			-- ind[e-> t];
			if (!ind[e-> t])
				tpo[tl ++] = e-> t;
		}
	}
	d[0] = 0;
	for (int ti = 0; ti < n; ++ ti) {
		int p(tpo[ti]), a;
		if (!hr[p]) {
			a = 0;
		}
		else {
			a = hr[p]-> t;
			for (edge* e = hr[p]-> next; e; e = e-> next)
				a = LCA(a, e-> t);
		}
		addEdge(ht, a, p);
		ath[p][0] = a;
		for (int i = 1; i < maxl; ++ i)
			ath[p][i] = ath[ath[p][i - 1]][i - 1];
		d[p] = d[a] + 1;
	}
	for (int ti = n - 1; ti >= 0; -- ti) {
		int p(tpo[ti]);
		sz[p] = 1;
		for (edge* e = ht[p]; e; e = e-> next)
			sz[p] += sz[e-> t];
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		int v;
		while (scanf("%d", &v), v) {
			addEdge(ha, v, i);
			addEdge(hr, i, v);
			++ oud[v];
			++ ind[i];
		}
	}
	topSort();
	for (int i = 1; i <= n; ++ i)
		printf("%d\n", sz[i] - 1);
}