https://www.zybuluo.com/ysner/note/1331590
---
##题面
[戳我][1]
##解析
一道挺不错的图论题。
###$50pts$算法
模拟。
$O(n^2)$暴力随便秒。
咕谷上居然有$70pts$。
```
il void dfs(re int u)
{
for(re int i=h[u];i+1;i=e[i].nxt)
{
re int v=e[i].to;
if(!--g[v]) ++ans,dfs(v);
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();
fp(i,1,n)
{
re int x=gi();
while(x)
{
add(x,i);++d[i];
x=gi();
}
}
fp(i,1,n)
{
fp(j,1,n) g[j]=d[j];
ans=0,dfs(i),printf("%d\n",ans);
}
return 0;
}
```
###$100pts$算法
一个点灭绝，要求其所有入度灭绝。
它所有入度灭绝，要求它所有入度的$lca$灭绝。
这样，就说明这个点对$lca$的灾难值有贡献。
什么，你说这不是树？
给所有入度为$0$的点加一个虚拟父亲不就是树了吗?
比较容易想到的$idea$，但这样复杂度还是$O(n^2)$。
考虑到如果一个点$u$单独对$lca$有贡献，那么所有对它有贡献的点也对$lca$有贡献。
这种关系实际为$lca$包含$u$，可以用树形结构中的父子关系体现。
于是我们可以依此关系重建树。
想想这是一张有向无环图，八成考拓扑排序。
那么就按拓扑序建树，每个点的父亲就是它所有入度点的$lca$。
$lca$必须用倍增求，因为这是动态维护信息。
这样建完树后，各点答案就是各点子树大小$-1$。
```
#include[ZJOI2012]灾难
原文：https://www.cnblogs.com/yanshannan/p/9903885.html
