题面
http://www.lydsy.com/JudgeOnline/upload/zjoi2012.pdf
题解
em…听说这叫支配树，好像很复杂的样子啊。。
于是学了一个DAG图的特殊情况就跑路了
可以发现，xxx会灭绝，当且仅当他的所有儿子都灭绝
然后他的儿子，又是一个子问题
考虑是树的话，那么就是所有儿子的LCA
但是这个不是树。。
那么就建成一棵树
具体来说
按拓扑序一个一个加入，每次加入一个点，他就作为他的所有食物的LCA的儿子
因为只有这个节点灭绝他才会灭绝
那么这样就是一颗树的结构了！！
答案就是子树节点个数-1
至于LCA，按树一样，到达一个点，就处理一下倍增数组就可以了
哦，对了，一开始先用一个虚根把所有度数为0的连起来
复杂度是O(nlogn)O(nlogn)O(nlogn)
CODE:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=70005;
int n;
vector<int> g[N],h[N];
queue<int> q;
int du[N];
int fa[N][21];
int dep[N];
vector<int> vec[N];
int lca (int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);for (int u=20;u>=0;u--)if (dep[fa[x][u]]>=dep[y])x=fa[x][u];if (x==y) return x;for (int u=20;u>=0;u--)if (fa[x][u]!=fa[y][u])x=fa[x][u],y=fa[y][u];return fa[x][0];
}
void topsort ()
{
for (int u=1;u<=n;u++){
if (du[u]==0){
h[u].push_back(n+1);g[n+1].push_back(u);du[u]++;}}q.push(n+1);dep[n+1]=1;int siz,x;while (!q.empty()){
x=q.front();q.pop();siz=g[x].size();for (int u=0;u<siz;u++){
du[g[x][u]]--;if (du[g[x][u]]==0) q.push(g[x][u]);}if (x!=n+1)//处理他的父亲什么的 {
siz=h[x].size();int now=h[x][0];for (int u=1;u<siz;u++) now=lca(now,h[x][u]);dep[x]=dep[now]+1;// printf("%d %d\n",now,x);vec[now].push_back(x);fa[x][0]=now;for (int u=1;u<=20;u++) fa[x][u]=fa[fa[x][u-1]][u-1];}}
}
int ans[N];
void dfs (int x)
{
int siz=vec[x].size();ans[x]=1;for (int u=0;u<siz;u++){
int y=vec[x][u];dfs(y);ans[x]=ans[x]+ans[y];}
}
int main()
{
scanf("%d",&n);for (int u=1;u<=n;u++){
int x;while (true){
scanf("%d",&x);if (x==0) break;du[u]++;g[x].push_back(u);h[u].push_back(x);}}topsort();dfs(n+1);for (int u=1;u<=n;u++) printf("%d\n",ans[u]-1);return 0;
}