目录
显示
题目链接
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; }