[洛谷 2597][ZJOI2012]灾难

题目链接

https://www.luogu.com.cn/problem/P2597

题解

我们发现，一个点灭绝当且仅当它的所有食物都灭绝，因此我们可以反向建边。

但是直接在原图上递推答案显然无法解决本题（导致一个点灭绝的点不一定是它的直接前驱点），因此我们需要重新建图。

我们希望我们建的图满足这样的特点：每个点都能挂在能导致它灭绝的最深的点的下面（这样建的图一定是个森林），这样我们只需统计每个点的子树大小，再减去一就是答案（扣掉它自己本身）。

要找到这样的位置，我们需要在原图上找出一个点的所有前驱节点的 LCA。

DAG 上的 LCA？其实原理和树上类似，我们只需在拓扑排序的时候预处理倍增数组就可以了。

#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> e[70005],e2[70005];
int fa[70005][25],f[70005],dep[70005],t[70005],siz[70005],n;
int lca(int x,int y)
{
 if(dep[x]>dep[y])swap(x,y);
 for(int i=16;i>=0;i--)
  if(dep[y]-dep[x]-(1<<i)>=0)y=fa[y][i];
 if(x==y)return x;
 for(int i=16;i>=0;i--)
  if(fa[x][i]!=fa[y][i])
  {
   x=fa[x][i];
   y=fa[y][i];
  }
 return fa[x][0];
}
void bfs()
{
 queue<int> q;
 memset(f,-1,sizeof(f));
 for(int i=1;i<=n;i++)
  if(!t[i])q.push(i),f[i]=0;
 while(!q.empty())
 {
  int u=q.front();
  q.pop();
  e2[f[u]].push_back(u);
  dep[u]=dep[f[u]]+1;
  fa[u][0]=f[u];
  for(int i=1;i<=16;i++)
   fa[u][i]=fa[fa[u][i-1]][i-1];
  for(auto v:e[u])
  {
   if(f[v]==-1)f[v]=u;
   else f[v]=lca(f[v],u);
   t[v]--;
   if(!t[v])q.push(v);
  }
 }
}
void dfs(int u)
{
 siz[u]=1;
 for(auto v:e2[u])
  dfs(v),siz[u]+=siz[v];
}
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  int v;
  while(cin>>v)
   if(!v)break;
   else e[v].push_back(i),t[i]++;
 }
 bfs();
 dfs(0);
 for(int i=1;i<=n;i++)
  cout<<siz[i]-1<<endl;
 return 0;
}