OJ题号：BZOJ2815、洛谷2597

思路：

先将所有的“生产者”连接至0号点“太阳”，然后用kahn求拓扑序。 、

易证一种生物会灭绝当且仅当他的所有食物均灭绝，

而所有食物均灭绝当且仅当他们的LCA灭绝。

按照拓扑序依次将各点加入新图，同时求该点所有食物的LCA，将该点作为LCA的儿子。

DFS遍历求各点后代数量。

注意倍增时不能直接循环到logN，而要循环到log2(dep)。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 inline int getint() { 7     int ch; 8     while(!isdigit(ch=getchar())); 9     int x=ch^'0';10     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');11     return x;12 }13 const int N=65535,logN=17;14 std::vector
          
            c[N],p[N];15 std::queue
           
             top;16 int anc[N][logN]={ 0},dep[N]={ 0},in[N]={ 0};17 void kahn(const int x) {18 std::queue
            
              q;19 q.push(x);20 while(!q.empty()) {21 int v=q.front();22 q.pop();23 top.push(v);24 for(unsigned int i=0;i
             

newc[N];31 inline void swap(int &a,int &b) {32 int t;33 t=a;34 a=b;35 b=t;36 }37 inline int LCA(int a,int b) {38 if(dep[a]

=0;i--) {40 if(dep[a]-(1<

=dep[b]) a=anc[a][i];41 }42 if(a==b) return a;43 for(int i=(int)log2(dep[a]);i>=0;i--) {44 if(anc[a][i]!=anc[b][i]) a=anc[a][i],b=anc[b][i];45 }46 return anc[a][0];47 }48 int ans[N]={ 0};49 void getans(const int x) {50 for(unsigned int i=0;i