一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。这个图没有环。图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。如果某个消费者的所有食物都灭绝了，它会跟着灭绝。我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。现在请你求出每一个物种的“灾难值”。

　　首先思考：什么情况下一个物种会灭绝？也就是所有它能吃的东西灭绝了，它就灭绝了。所以如果要让物种A灭绝，我们可以选一个物种B，使得物种A所有能吃的东西都灭绝。我们定义”灭绝树”，其中一个节点的父亲是能让它灭绝的深度最低的结点。不难发现灭绝树上A的祖先灭绝后，A一定灭绝。所以若要让物种x，y一起灭绝，只需查询它们所有父亲在灭绝树上的lca即可。

　　这道题做了三天。。最后用cyaron对拍出来，发现是一个以前写的模块忘记改回来了。。以后写程序就要一口气写完，不要被外界干扰。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 const int maxn=1000000;  8   9 int first1[maxn], first2[maxn], topo[maxn], topo2[maxn], out[maxn]; 10 int fa[maxn][30], dep[maxn], size[maxn], ans[maxn]; 11 struct Edge{ 12     int v, to, next; 13 }; 14 Edge edges1[maxn], edges2[maxn]; 15  16 int n, cnte1, cnte2; 17  18 void addedge(int *first, Edge *edges, int &cntedge, 19              int v, int from, int to){ 20     edges[cntedge].v=v; 21     edges[cntedge].to=to; 22     edges[cntedge].next=first[from]; 23     first[from]=cntedge; 24     cntedge++; 25     return; 26 } 27  28 double log2(int x){ 29     return log(x)/log(2); 30 } 31  32 int get_lca(int x, int y){ 33     int t=0, step=1; 34     if (dep[x]
         
          >=1; 39         ++step; 40     } 41     for (int step=20; step>0; --step){ 42         if (fa[x][step]!=fa[y][step]){ 43             x=fa[x][step]; 44             y=fa[y][step]; 45         } 46     } 47     if (x!=y) x=fa[x][1]; 48     return x; 49 } 50  51 int main(){ 52     for (int i=0; i
          

q; 65 for (int i=1; i<=n; ++i){ 66 if (!out[i]){ 67 addedge(first1, edges1, cnte1, 1, i, 0); 68 addedge(first2, edges2, cnte2, 1, 0, i); 69 out[i]=1; 70 } 71 } 72 //以上：读入、加边 73 q.push(0); 74 int nownode, nowedge, nowson; 75 for (int i=0; i<=n; ++i){ 76 nownode=q.front(); 77 q.pop(); 78 topo[i]=nownode; 79 nowedge=first2[nownode]; 80 while (nowedge!=-1){ 81 nowson=edges2[nowedge].to; 82 if (!--out[nowson]){ 83 q.push(nowson); 84 } 85 nowedge=edges2[nowedge].next; 86 } 87 } 88 //以上：拓扑排序 89 int lca=0, cur=0; 90 for (int i=1; i<=n; ++i){ 91 nownode=topo[i]; 92 nowedge=first1[nownode]; 93 lca=nowson=edges1[nowedge].to; 94 nowedge=edges1[nowedge].next; 95 while (nowedge!=-1){ 96 nowson=edges1[nowedge].to; 97 //if (!nowedge) break; !!!! 98 lca=get_lca(lca, nowson); 99 nowedge=edges1[nowedge].next;100 }101 dep[nownode]=dep[lca]+1;102 cur=0;103 fa[nownode][cur]=nownode;104 fa[nownode][++cur]=lca;105 ++size[lca];106 while (fa[nownode][cur]){107 fa[nownode][cur+1]=fa[fa[nownode][cur]][cur];108 ++cur;109 }110 }111 //以上：建立灭绝树112 while (!q.empty()) q.pop();113 for (int i=0; i<=n; ++i){114 ans[i]=1;115 if (size[i]==0) q.push(i);116 }117 int fath;118 for (int i=n; i>0; --i){119 nownode=q.front();120 q.pop();121 fath=fa[nownode][1];122 --size[fath];123 if (!size[fath]) q.push(fath);124 ans[fath]+=ans[nownode];125 }126 //以上：统计size127 for (int i=1; i<=n; ++i)128 printf("%d\n", ans[i]-1);129 return 0;130 }