简要题意：
给一个有向无环图，问每个节点删掉之后会导致多少个点不可达。
似乎以前拿来考过….
我们定义一棵树，它满足对应点造成的灭绝值即为当点的子树大小-1
按照被捕食者—>捕食者的关系拓扑排序，然后依次建树，建到当前点的时候可以作为当前生物食物的点应当已经在树中了。如果当前点代表的生物要灭亡，很好理解那么可以作为它食物的生物都要灭亡，所以将这个点丢到它的可以作为它食物的生物的所有点的最近$LCA$点之下就可以了，可以用倍增$LCA$来维护动态加点。
为了方便，可以令一个点作为所有生产者的根。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 100100 10 #define llg int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,e[maxn],du[maxn],dl[maxn],tpx[maxn],deep[maxn],f[maxn][22],size[maxn]; 13 vector<llg>a[maxn],c[maxn],g[maxn]; 14 void in(llg x) 15 { 16 llg d; 17 while (1) 18 { 19 scanf("%d",&d); 20 if (d==0) break; 21 du[x]++; 22 a[d].push_back(x); 23 c[x].push_back(d); 24 } 25 } 26 27 void TP() 28 { 29 dl[1]=n+1; 30 llg head=0,tail=1,x,v,w,cnt=0; 31 do 32 { 33 x=dl[++head]; 34 w=a[x].size(); 35 tpx[x]=++cnt; 36 for (llg i=0;i<w;i++) 37 { 38 v=a[x][i]; 39 du[v]--; 40 if (du[v]==0) 41 { 42 dl[++tail]=v; 43 } 44 } 45 }while (head!=tail); 46 } 47 48 bool cmp(llg a,llg b){return tpx[a]<tpx[b];} 49 50 void make_f(llg x) {for (llg i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];} 51 52 llg find(llg x,llg y) 53 { 54 if (deep[x]<deep[y]) swap(x,y); 55 for (llg i=20;i>=0;i--) 56 if (deep[f[x][i]]>=deep[y]) 57 x=f[x][i]; 58 if (x==y) return x; 59 for (llg i=20;i>=0;i--) 60 if (f[x][i]!=f[y][i]) 61 x=f[x][i],y=f[y][i]; 62 return f[x][0]; 63 } 64 65 void work(llg x) 66 { 67 llg ro; 68 if (c[x].size()==1) ro=c[x][0]; 69 else 70 { 71 llg w=c[x].size(); 72 ro=find(c[x][1],c[x][0]); 73 for (llg i=2;i<w;i++) ro=find(ro,c[x][i]); 74 } 75 f[x][0]=ro; deep[x]=deep[ro]+1; 76 g[ro].push_back(x); 77 make_f(x); 78 } 79 80 void dfs(llg x) 81 { 82 llg w=g[x].size(); 83 size[x]=1; 84 for (llg i=0;i<w;i++) 85 { 86 dfs(g[x][i]); 87 size[x]+=size[g[x][i]]; 88 } 89 } 90 91 int main() 92 { 93 yyj("catas"); 94 cin>>n; 95 for (llg i=1;i<=n;i++) in(i); 96 for (llg i=1;i<=n;i++) 97 if (du[i]==0) 98 { 99 du[i]++; 100 c[i].push_back(n+1); 101 a[n+1].push_back(i); 102 } 103 TP(); 104 for (llg i=1;i<=n+1;i++) e[i]=i; 105 sort(e+1,e+n+1,cmp); 106 deep[n+1]=1; 107 for (llg i=1;i<=n;i++) 108 work(e[i]); 109 dfs(n+1); 110 for (llg i=1;i<=n;i++) printf("%d ",size[i]-1); 111 return 0; 112 }