BZOJ 2815。
解法还是挺巧妙的。
放上写得很详细很好懂的题解链接 戳这里。
一个物种$x$如果要灭绝，那么沿着它的入边反向走走走，一定可以走到一个点$y$，如果这个点$y$的物种灭绝了，那么$x$也一定会灭绝。而且，因为一次只能灭绝一个物种，只有满足这个条件这个物种$x$才会灭绝。
那么我们可以考虑建立一棵树，对于一个点$x$，将它能直接导致灭绝的点$y$作为它的直接儿子，然后我们统计一下每一个结点的$siz$再$- 1$就是答案了。
考虑一下如何找到这个走走走之后的关键点，因为这张图满足$DAG$的性质，我们可以一边拓扑排序一边建树，如果当前从队列里面取出了$x$，那么所有在$x$之前能走到的点一定在我们建的树里面了，我们只要在建好的树上找到所有直接连通$x$的点的$lca$作$x$的父亲就可以了。
插点的倍增$lca$，可以直接动态维护出来。
可以建一个超级源点连通所有的连通块。
时间复杂度$O(nlogn)$。
Code：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std; const int N = 1e5 + ;
const int Lg = ; int n, rt, tot = , head[N];
int q[N], fa[N][Lg], dep[N], deg[N], siz[N];
vector <int> G1[N], G2[N]; struct Edge {
int to, nxt;
} e[N << ]; inline void add(int from, int to) {
e[++tot].to = to;
e[tot].nxt = head[from];
head[from] = tot;
} inline void read(int &X) {
X = ; char ch = ; int op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void swap(int &x, int &y) {
int t = x; x = y; y = t;
} inline void prework(int x, int fat) {
dep[x] = dep[fat] + , fa[x][] = fat;
for(int i = ; i <= ; i++)
fa[x][i] = fa[fa[x][i - ]][i - ];
} inline int getLca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = ; i >= ; i--)
if(dep[fa[x][i]] >= dep[y])
x = fa[x][i];
if(x == y) return x;
for(int i = ; i >= ; i--)
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][];
} inline void topSort() {
int l = , r = ; q[] = rt;
prework(rt, );
for(; l <= r; ) {
int x = q[++l], fat = , vecSiz = G2[x].size();
for(int i = ; i < vecSiz; i++) {
int y = G2[x][i];
if(!fat) fat = y;
else fat = getLca(fat, y);
}
if(x != rt) add(x, fat), add(fat, x);
prework(x, fat); vecSiz = G1[x].size();
for(int i = ; i < vecSiz; i++) {
int y = G1[x][i];
--deg[y];
if(!deg[y]) q[++r] = y;
}
}
} void dfs(int x, int fat) {
siz[x] = ;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fat) continue;
dfs(y, x);
siz[x] += siz[y];
}
} int main() {
read(n);
for(int x, i = ; i <= n; i++) {
for(read(x); x; read(x)) {
G1[x].push_back(i);
G2[i].push_back(x);
++deg[i];
}
} rt = n + ;
for(int i = ; i <= n; i++)
if(!deg[i]) {
G1[rt].push_back(i);
G2[i].push_back(rt);
++deg[i];
} topSort();
dfs(rt, ); for(int i = ; i <= n; i++)
printf("%d\n", siz[i] - ); return ;
}