挺不错的一个构造题。

如果食物链是一个树，怎么办？

一个点灭绝，灾难就是子树大小-1

但是这个是一个DAG。样例中的图片就不是树。

能不能变成树？

一个点灭绝，引发的后续事情太多，不好考虑。

反过来想，一个点灭绝原因。

发现，一个点灭绝的前提是，所有前驱都灭绝。

一次只能灭绝一个。

如果前驱多个的话，显然灭绝一个该点不会灭绝。

所以，继续找前驱的前驱。

直到前驱变成一个点P。那么，就相当于，这个点灭绝了，开始说的点X才会灭绝。

如果我们构造出来一个树，那么这个P就是X的所有前驱的LCA

找到所有前驱的LCA，直接把X作为LCA的儿子连上去。就构造出来了这个树。

其实，就是最近的可以灭绝后灭绝X的点。

然后一个点的灾难就是子树大小。

正确性显然：某个物种灭绝的前提是，该物种的树上的祖先灭绝一个。

但是可能开始有多个入度为0的点。

就建立一个超级根root，入度为0的点都是它的儿子。

root不参与答案统计。如果连向root的点，无论如何不会因为某个物种灭绝而灭绝。（因为多于一个前驱必须自己死）

 

代码：

#include
     
      using namespace std;typedef long long ll;const int N=65534+6;int n;int fa[N][18];struct node{    int nxt,to;}e[300000],bian[300000];int hd[N],cnt;int pre[N],tot;int rt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}void upda(int x,int y){    bian[++tot].nxt=pre[x];    bian[tot].to=y;    pre[x]=tot;}int du[N];int q[2*N],l,r;int dep[N];int sz[N];vector
      
       eat[N];int lca(int x,int y){    //cout<<" lca "<
       
        <<" and  "<
        
         <
         
          =0;j--){        if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];    }    if(x==y) return x;//    cout<
          
           <<" aaa "<
           
            <
            
             =0;j--){ if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; } return fa[x][0];}void topo(){ l=1; for(int i=1;i<=n;i++){ if(du[i]==0){ q[++r]=i; upda(rt,i); fa[i][0]=rt;//warning!!! dep[i]=1; } } while(l<=r){ int x=q[l++]; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; du[y]--; if(du[y]==0){ int las=-1; for(int j=0;j<(int)eat[y].size();j++){ int z=eat[y][j]; if(las==-1) las=z; else las=lca(las,z); } upda(las,y); fa[y][0]=las; dep[y]=dep[las]+1; for(int j=1;j<=17;j++){ fa[y][j]=fa[fa[y][j-1]][j-1]; } q[++r]=y; } } }}void dfs(int x){ sz[x]=1; for(int i=pre[x];i;i=bian[i].nxt){ int y=bian[i].to; dfs(y); sz[x]+=sz[y]; }}int main(){ scanf("%d",&n); rt=n+1; dep[0]=-1; dep[rt]=0; for(int i=1;i<=n;i++){ int t=0; while(1){ scanf("%d",&t); if(!t) break; eat[i].push_back(t); add(t,i); du[i]++; } } topo(); dfs(rt); //cout<
             
              <
             
            
           
          
         
        
       
      
     

 

总结：

突破口就是想到转化成树比较好处理。然后考虑一个物种是怎么灭绝的。

发现，一个物种灭绝，只要找到最近的可以让它灭绝的物种Y即可。所有能让Y灭绝的物种也能让X灭绝。

而一个物种灭绝后，可能影响到多个物种也灭绝。

一个点，一个前驱，多个后继。

这就是树形结构！！

---

 

upda：2019.5.6:

这个东西是DAG的支配树，，，，

所以其实是模板题。

但是2012年应该还没什么人知道。