<div class="post_brief"><p>
灭绝树的模板题么。之前不知道这题，差点当原创题出出去了。</p>

 

好像有不少人不知道这东西的样子？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", &amp;n);
for (int i = 1; i &lt;= n; ++ i) {
	int v;
	while (scanf("%d", &amp;v), v) {
		addEdge(ha, v, i);
		addEdge(hr, i, v);
		++ oud[v];
		++ ind[i];
	}
}
topSort();
for (int i = 1; i &lt;= n; ++ i)
	printf("%d\n", sz[i] - 1);



}