首先,我们需要把图上的边像样例的图片一样反着建。

然后我们跑一遍拓扑排序(注意这时候可能有多个入度为0的点),记录每个点的层数(即它的所有父亲的层数最大值+1)。

然后我们将所有点按层数升序排序,依次处理。

对于每个点,能够使它灭绝的,深度最大的点是它所有父亲的\(LCA\),记为\(f_{i,0}\)。

当然必然会有某一些点的所有父亲没有\(LCA\),或者它干脆没有父亲(①)。

这里就是要按层数处理节点的原因,可以确保处理一个点时,它所有的父亲都被处理过了。

显然\(f_{f_{i,0},0},f_{f_{f_{i,0},0},0},...\)也能使\(i\)灭绝。

由于\(f_{i,0}\)是唯一的,所以如果我们建一个新的图,其中所有\(f_{i,0}\)向\(i\)连边,就得到了一个森林。

森林中所有树的根都满足①,而且所有满足①的点必然是树根。

而一个点的灾难值就是它的子树中点的数量。

code:

#include
    
     using namespace std;int n,t,in[65551],sq[65551],sz,f[65551][20],ans[65551],dep[65551],tg;vector
     
      e[65551];vector
      
       fs[65551];vector
       
        ze[65551];queue
        
         q;void Tpst(){    for(int i=1;i<=n;i++)if(!in[i])q.push(i);    while(!q.empty()){        sq[++sz]=t=q.front();        q.pop();        for(int i=0;i
         
          =0;i--)if(dep[x]-(1<
          
           =dep[y])x=f[x][i]; for(int i=16;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; if(x==y)return x; return f[x][0];}void dfs(int x){ ans[x]=1; for(int i=0;i