3
admin LV 10 SU @ 2025-11-5 20:03:54
P2597[灾难]

更好的阅读体验

2020.9.18 Update:修改了代码里的入队一个小 bug

题目简述
- 输入一个有向森林
- 灾难值：在一个节点被删去后以它为根从上到下逐步删去入度为0的点，最终被删去的点的数量即其灾难值
- 你需要输出每个点的灾难值
比如看样例（一个食物网应该是由食物指向捕食者，在存边时要反向存）![]

1节点被删去后2、3节点入度变为0被删去，接着4、5节点入度变为0被删去，一共4个点被删去，所以它的灾难值是4.

2被删去会使5节点入度为0被删去，所以它的灾难值为1。剩下几个点被删去都不会产生入度为0的点，他们灾难值为0

题目分析

下面内容来自《中学生计算机程序设计提高篇》（有删减）

对于生产者，不妨给它添加一个假想的食物——太阳。那么这个森林就变成了一颗“灭绝树”。

首先，按照食物网从猎物到捕食者的顺序拓扑排序，有且仅有太阳没有任何入度，所以先将太阳加入灭绝树，之后，依次考虑每个生物 $i$ ,依次考虑构建好排序在 $i$ 之前的生物组成的灭绝树，假设 $i$ 的食物有 $p_1,p_2,p_3,\cdots,p_k$ (这些节点在拓扑序中比 $i$ 靠前， $i$ 会灭绝，当且仅当 $p_1,p_2,p_3,\cdots,p_k$ 全部灭绝，当且仅当LCA（ $p_1,p_2,p_3,\cdots,p_k$ ）灭绝。

于是可以在树上加上LCA到 $i$ 的边，把 $i$ 的边加到树中。处理完后就得到了灭绝树，每个生物的灾难值就是以它为根的子树大小减一

下面是自己的详细理解和对上面的补充

感觉书中说的并不是非常清楚，至少我在设计思路和完成代码时遇到了很多问题（WA了10次的痛）

本题中的LCA和普通LCA有一些差别，1是它是多节点的LCA，再者它是要一边建树一边LCA。而且本题中涉及原树（食物网）和新树（灭绝树），书中没有说在哪里求LCA，如何倍增。

我想到的一种求LCA的方法是：更新迭代LCA

其思路是：给每个数多维护一个值 $dad$ ,用来表示如果此时它要被连入灭绝树中，它应该是哪个点的儿子。一开始将 $dad$ 清为-1，将开始入度为0的点 $p_i$ 的 $dad$ 设为0（太阳）。在拓扑排序取出一个点 $i$ 的时候连接边 $dad[i]->i$ (此时 $i$ 的父亲（根节点的父亲前面已经确定）都已经被处理过了，所以 $dad[i]$ 已经确定（怎么确定的马上会说））。然后更新点 $i$ 相对应的深度和倍增数组（因为 $i$ 的祖先们已经在 $i$ 之前被确定，所以此时的深度和其倍增数组可以唯一确定），接着遍历 $i$ 的儿子们，如果它的儿子 $p$ 的父亲 $dad[p]$ 为0，说明它的父亲还没有被更新过，此时把 $dad[p]$ 更新为 $i$ 。否则就将 $dad[p]$ 更新为LCA（ $dad[p],i$ ）。这样，在遍历到 $p$ 的时候它的父节点就被确定下来了。

为什么能这样做呢？

我们需要在求出在原树上 $i$ 的所有父亲的LCA，就相当于把两个父亲当成一组，一组一组地求LCA，并把这个过程转移到一个点遍历其儿子的时候。

思路总结
1. 初始化 $dad$ 数组为-1。
2. 读入原树，反向建立森林并统计每个点的入度。
3. 扫描所有点，将入度为0的点加入队列中，并将其 $dad$ 更新为0。
4. 拓扑排序，取出队首 $x$ ，连接 $dad[x],x$ ,并更新倍增数组和该点深度。遍历 $x$ 的儿子，更新儿子的 $dad$ 并将儿子的入度减一，若入度为0则入队。
5. 重复操作4，直到队列为空。
6. $dfs$ 一次新树，并递归求子树大小。
7. 输出每个点子树减一
易错点
- 原树是一个有向无环森林，亲测存边数组大小20w能过
- 倍增数组在根节点再往上是0（如果把太阳设为-1节点就会WA第五个点）
- 存原树时要反向存
- 倍增深度16
- 原树和新树的查询小心弄混
- 输出时子树大小要减一
代码实现
```
#include<bits/stdc++.h>
#define N 65536
using namespace std;
int n,tot,ans,tot1;
int to[N*4],ne[N*4],head[N];//原树邻接表 
int edge[N],anc[N][21],dad[N],size[N],de[N];// 入度、倍增、父亲、子树大小、深度 
int to1[N*4],ne1[N*4],head1[N];//新树邻接表 
void add(int x,int y) { to[++tot]=y,ne[tot]=head[x],head[x]=tot,edge[y]++; }//存原树 
void add1(int x,int y) { to1[++tot1]=y,ne1[tot1]=head1[x],head1[x]=tot1;}//存新树 
queue < int > q;//STL队列 
void dfs(int x){//深搜求子树大小 
    size[x]=1;
    for(int i=head1[x];i;i=ne1[i]){
        int y=to1[i];
        dfs(y);
        size[x]+=size[y];
    } 
}
int lca(int x,int y){//求LCA 
    if(x==y) return x;
    if(de[x]<de[y]) swap(x,y);
    for(int i=18;i>=0;i--) if(de[anc[x][i]]>=de[y]) x=anc[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return anc[x][0];
}
void read(int &x) {//快读 
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}
int main()
{
    read(n);
    for(int i=1;i<N;i++) dad[i]=-1;//初始化 
    for(int i=1;i<=n;i++){
        int x;
        read(x);
        while(x){
            add(x,i);//反向存树 
            read(x);
        }
    }
    for(int i=1;i<=n;i++) 
        if(!edge[i]){
            q.push(i);
            dad[i]=0;//找到入度为0的边 
        }
    while(!q.empty()){
        int x;
        x=q.front();q.pop();//取出队首  
        add1(dad[x],x);
        anc[x][0]=dad[x],de[x]=de[dad[x]]+1;        
        for(int i=1;i<=18;i++) anc[x][i]=anc[anc[x][i-1]][i-1];//更新倍增数组 
        for(int i=head[x];i;i=ne[i]){
            int y=to[i];
            if(dad[y]==-1) dad[y]=x;//父亲之前没有被更新 
            else dad[y]=lca(dad[y],x);//父亲之前已经被更新过 
            if(--edge[y]==0) q.push(y);//入度为0则入队 
        }
    }
    dfs(0);//求子树大小 
    for(int i=1;i<=n;i++)
        printf("%d\n",size[i]-1);//输出 
    return 0;
}
	
```
写题解不易，给个赞呗

zhengziye LV 8 @ 2026-7-14 15:51:15

投诉

差评！！！为什么生地会考完还要学习生物？！气死我嘞！！！

暴力

如果照原来题目给出的数据来建图很难解决，连暴力都无法做到。那么不如反向建边，这样就是以能量流动的方向为方向，这样就可以暴力了！！！一个一个模拟生物灭绝就可以获得 $\textcolor{#B0D628}{80}$ 分的高分。（也许过几天就加强数据了，可能就没这么高了）

$\textcolor{#B0D628}{80}$ 分暴力代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1<<16;
int n;
vector<int>a[N];
int fd[N],rd[N],ans=0;
inline void dfs(int x){
	for(int y:a[x]){
		fd[y]--;
		if(!fd[y]&&rd[y])
			dfs(y),ans++;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		while(cin>>x){
			if(x==0)break;
			a[x].emplace_back(i);
			rd[i]++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)fd[j]=rd[j];
		ans=0;
		dfs(i);
		cout<<ans<<"\n";
	}
	return 0;
}

优化

接下来，想想怎么优化。众所周知，地球上任何食物链的能量最终来源都是太阳。所以我们可以换一种思路，以节点 $0$ （太阳）为根，建一棵树。要建成什么样 ~~的社会主义国家~~，怎么建 ~~设社会主义国家~~ 呢？

什么样

我们通过题目要求输出来反推，题目要求输出该生物灭绝后导致的灭绝物种数量。则我们可以让每个节点的父亲节点为使得当前节点生物灭绝的经过其他生物最少的生物节点，这样表示就可以使每个节点的任意一个祖先灭绝后该点生物必定灭绝，每个节点生物灭绝后，以该节点为根的子树必定全部灭绝。

怎么建

先将原图的父亲节点记录下来，如果只有一个父亲，那么原来的父亲就是现在树的父亲，如果有多个父亲节点 ~~《中华人民共和国婚姻法》确立了一夫一妻制为我国基本婚姻制度~~ ，那么就寻找这几个父亲的最近公共祖先，则这个公共祖先灭绝后，这个节点的所有父亲都会灭绝，则这个节点就会灭绝。

后续

于是我们有了正确思路，再搭配倍增进行优化，就可以 $\textcolor{green}{Accepted}$ ！！！

$\textcolor{green}{AC}$ 代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1<<16;
int n;
int fa[N],rd[N],f[N][21],dep[N],siz[N];//父亲，入度，祖先倍增表，深度，子树大小 
vector<int>G1[N],G2[N];//原来的森林和后来记录的灭绝树 
inline void dfs(int x){//计算树的深度 
	siz[x]=1;
	for(int y:G2[x]){
		dfs(y);
		siz[x]+=siz[y];
	}
}
inline int LCA(int u,int v){//倍增LCA
	if(u==v)return u;
	if(dep[u]<dep[v])swap(u,v);
	for(int i=18;i>=0;i--)
		if(dep[f[u][i]]>=dep[v])
			u=f[u][i];
	if(u==v)return v;
	for(int i=18;i>=0;i--)
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	return f[u][0];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(fa,-1,sizeof fa);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		while(cin>>x){
			if(!x)break;
			G1[x].emplace_back(i);//反向建边，也就是以能量流动的方向为方向（可恶，该死的生物课记忆） 
			rd[i]++;
		}
	}
	queue<int>Q;
	for(int i=1;i<=n;i++)
		if(!rd[i]){//如果入度为0，就加入队列，并以太阳0为父亲（地球上能量的最终来源都是太阳） 
			Q.push(i);
			fa[i]=0;
		}
	while(Q.size()){//记录灭绝树（即使得后来树的每个节点的父亲灭绝后，自己一定灭绝） 
		int x=Q.front();
		Q.pop();
		G2[fa[x]].emplace_back(x);
		f[x][0]=fa[x];
		dep[x]=dep[fa[x]]+1;
		for(int i=1;i<=18;i++)
			f[x][i]=f[f[x][i-1]][i-1];
		for(int y:G1[x]){
			if(fa[y]==-1)fa[y]=x;//父亲没有被更新过 
			else fa[y]=LCA(fa[y],x);//父亲已经被更新过 
			if(--rd[y]==0)Q.push(y);//入度为0则入队 
		}
	}
	dfs(0);
	for(int i=1;i<=n;i++)
		cout<<siz[i]-1<<"\n";//不能包括自己，所以字数大小-1个就是危险指数 
}

Hansang1 LV 9 MOD @ 2026-7-14 15:25:53

自己场切的第一道蓝？说下思路。

1.一开始想的点双联通，从食物到消费者建边，强行把有向图迁移成无向图，

求出割点后再跑一遍求子树大小，调了半小时 20 分 GG。

2.观察到 n 刚好是 $2^16$ ，考虑带 log 的做法，估计是 LCA。

而 LCA 必须在树上进行，题目给的图加了超级源点都不是树，看来得重建一颗。

3.答案应该也是子树大小，树边来自于依赖关系。

考虑点 $x$ 对于点 $y$ 的依赖，即点 $y$ 消失后点 $x$ 就一定灭绝。

当且仅当点 $y$ 是点 $x$ 所有食物的 LCA。

4.一个个枚举点求食物 LCA 肯定不现实，时间复杂度 $O(N^2logN)$ 。

因为原图有严格的层次关系，考虑一层层拓扑，当一个点的入度为 0，就可以建立依赖并入队。

5.最后在依赖树里求每个节点的子树大小 - 1。

6.时间复杂度平均， $M$ 最大可以到 $N^2$ 。

但题目说输入的文件大小不超过 1 MB，1 MB = 1,048,576 字节，除以两个点为 524,288。

即 $M$ 最大为 $5e5$ ，实际上因为拓扑过程中就路径压缩， $M$ 会更小。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 66000;

vector<int> G[N], cg[N];

int f[N][25], rd[N], dep[N], bfa[N];

int LCA(int x, int y) {
	if ((x == 0) || (y == 0)) {
		return 0;
	}
	if (dep[x] < dep[y]) {
		swap(x, y);
	}
	for (int i = 20; i >= 0; i --) {
		if (dep[f[x][i]] >= dep[y]) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20; i >= 0; i --) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}

bool v[N];
int siz[N];

void dfst(int x) {
	siz[x] = 1;
	v[x] = 1;
	for (int y : cg[x]) {
		dfst(y);
		siz[x] += siz[y];
	}
}

queue<int> Q;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	memset(rd, 0, sizeof(rd));
	for (int i = 1; i <= n; i ++) {
		bfa[i] = i;
		int x;
		while (cin >> x) {
			if (x == 0) {
				break;
			}
			G[x].push_back(i);
			rd[i] ++; 
		}
	}
	
	memset(dep, 0, sizeof(dep));
	for (int i = 0; i <= n; i ++) {
		for (int j = 0; j <= 20; j ++) {
			f[i][j] = -1;
		}
	}
	for (int i = 1; i <= n; i ++) if (rd[i] == 0) {
		G[0].push_back(i);
		rd[i] ++;
	}
	Q.push(0);
	
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (int y : G[x]) if (rd[y]) {
			if (x == 0) {
				f[y][0] = 0;
			}
			else {
				if (f[y][0] == -1) {
					f[y][0] = x;
				}
				else {
					if (f[y][0] != 0) {
						f[y][0] = LCA(x, f[y][0]);
					}
				}
			}
			rd[y] --;
			if (rd[y] == 0) {
				Q.push(y);
				cg[f[y][0]].push_back(y);
				dep[y] = dep[f[y][0]] + 1;
				for (int i = 1; i <= 20; i ++) {
					f[y][i] = f[f[y][i - 1]][i - 1];
				} 
			}
		}
	}
	
	memset(v, 0, sizeof(v));
	memset(siz, 0, sizeof(siz));
	for (int i = 1; i <= n; i ++) if (v[i] == 0) {
		dfst(i);
	}
	
	for (int i = 1; i <= n; i ++) {
		cout << (siz[i] - 1) << "\n";
	}

    return 0;
}

2
yanchengyi2024 LV 9 @ 2026-7-14 15:04:25
赛时打了一个暴力，拿下80分，数据太水

思路

刚刚生地会考完的我回忆起之前的知识，好像说所有的生产者（入度为 $0$ 的点）的能量来源是太阳，我们不妨可以建立一个 $0$ 号点表示太阳，并将其与所有的生产者链接起来。如果一个生物想要灭绝（为什么会有“想要灭绝”这种说法？），他的所有食物都得灭绝，也就是说它所有的食物的最近公共祖先都得灭绝。拿样例举例，如果小强（人名）想要灭绝（？），牛和羊就得灭绝，他们的最近公共祖先是草，所以就需要草灭绝。

但是这又不是一颗树，如何求最近公共祖先？（卖个关子）

我们把题目翻译一遍，一个物种想要灭绝，需要让能量流动的网中他的入度为零，既然有“入度为零”，自然想到拓扑排序。我们在拓扑排序的同时进行建树。对于一个节点 $x$ ，遍历他的子节点 $y$ （吃他的生物），将 $fa_y$ 赋值为 $x$ 。但是这有一个问题：同一个节点可能会出现多个父亲，如何解决？还记得之前说的“食物的最近公共祖先”结论吗？由此我们可以得出对于同一个节点的多个父亲，他的“真父亲”是所有“假父亲”的最近公共祖先。再次回归之前那个问题，一个图上如何求最近公共祖先？如果我们能访问到一个点，说明它的父辈们都已经处理好了，他们的 $fa$ 也是正常的，这不就可以进行 $lca$ 了吗？

最后，只需要在这个树上统计每一个节点的子树大小（子树内的点都以这个点为 $fa$ ，所以它灭绝后一定都会灭绝），在除去自己本身，即为答案。

相关知识点：
不会最近公共祖先的出门左转
不会拓扑排序的出门右转

啊，终于写完了，累死我了。

AC代码
```
#include<bits/stdc++.h>
using namespace std;
template<typename T>void qr(T &x)//感觉输入会很大，开一个快读 
{
	x=0;int f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(; isdigit(c);c=getchar())x=x*10+c-'0';
	x=x*f;
}
const int N=66000;
int n,ans;
vector<int>G[N],G2[N];
int rd[N],st[N][20],fa[N],siz[N],dep[N];//入度，最近公共祖先倍增数组，父亲节点，子树大小，节点深度 
queue<int>Q;
void dfs(int x)//统计子树大小 
{
	siz[x]=1;
	for(int i:G2[x])
	{
		dfs(i);
		siz[x]+=siz[i];
	}
}
int lca(int x,int y)//求LCA 
{
	if(x==y)return x;
	if(dep[x]<dep[y])swap(x,y);
	for(int i=18;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
	return st[x][0];
}
int main()
{
	qr(n);
	memset(fa,-1,sizeof(fa));
	for(int i=1;i<=n;i++)
	{
		int x=1;
		while(x>0)
		{
			qr(x);
			if(x!=0)G[x].push_back(i),rd[i]++;//入度++ 
		}
	}
	for(int i=1;i<=n;i++)if(!rd[i])
	{
		Q.push(i);//生产者们 
		fa[i]=0;//0即为阳光 
	}
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		G2[fa[x]].push_back(x);//建边 
		st[x][0]=fa[x];dep[x]=dep[fa[x]]+1;
		for(int i=1;i<=18;i++)st[x][i]=st[st[x][i-1]][i-1];//记录倍增数组 
		for(int y:G[x])
		{
			if(fa[y]==-1)fa[y]=x;//如果没有fa，就先赋值 
			else fa[y]=lca(fa[y],x);//如果有，就LCA 
			//lca(x,y,z)=lca(lca(x,y),z) 
			rd[y]--;
			if(rd[y]==0)Q.push(y);//拓扑 
		}
	}
	dfs(0);
	for(int i=1;i<=n;i++)printf("%d\n",siz[i]-1);//输出答案 
	return 0;//完结撒花！ 
}
```
投诉

为什么生地会考完还要学生物！！！

dengyanzhi2024 LV 8 @ 2026-7-14 15:37:51

#include<bits/stdc++.h>
using namespace std;
const int N = 65540;
int n;
vector<int> G[N], G1[N];
int rd[N], st[N][20], fa[N], siz[N], dep[N];
queue<int> q;

void dfs(int x)
{
    siz[x] = 1;
    for (auto y : G1[x])
        dfs(y), siz[x] += siz[y];
}

int lca(int x, int y)
{
    if (x == y) return x;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 18; i >= 0; i--) if (dep[st[x][i]] >= dep[y]) x = st[x][i];
    if (x == y) return x;
    for (int i = 18; i >= 0; i--) if (st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];
    return st[x][0];
}

int main()
{
    cin >> n;
    for (int i = 1; i < N; i++) fa[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        int x = 114514;
        while (x != 0)
        {
            cin >> x;
            if(x) G[x].push_back(i), rd[i] ++;
        }
    }   

    for (int i = 1; i <= n; i++)
        if (rd[i] == 0)
            q.push(i), fa[i] = 0;
    while (q.size())
    {
        int x = q.front(); q.pop();
        G1[fa[x]].push_back(x);
        st[x][0] = fa[x]; dep[x] = dep[fa[x]] + 1;
        for (int i = 1; i <= 18; i++) st[x][i] = st[st[x][i-1]][i-1];
        for (auto y : G[x])
        {
            if (fa[y] == -1) fa[y] = x;
            else fa[y] = lca(fa[y], x);
            if (--rd[y] == 0) q.push(y);
        }
    }
    dfs(0);
    for (int i = 1; i <= n; i++) cout << siz[i] - 1 << '\n';
    return 0;
}

0
qinkaiwen LV 10 MOD @ 2026-7-14 14:59:09
出题人是如何做到在 DAG 上用 LCA 的？

好吧模拟赛时并不知道要用 LCA，去想 bitset 优化暴力了。不过最后发现了一些性质然后场切了。

这里考虑到有很多个入度为 $0$ 的点于是开了个点 $0$ 连接，保证所谓的“图根”只有一个。

考虑样例：首先，单删除点 $2$ 无法去除 $4$ 的连通性，点 $3$ 同理。这其实等价于直接在从 $1$ 连一条有向边到点 $4$ 。

然后我就在想能不能每个点开个集合通过类似 bfs 的方式不断删点加入它的所有父节点直到剩下一个点。很明显这是 $O(n^2)$ 的。

但是这个集合最后剩下的点是有什么特殊的性质呢？其实这个点是当前节点通过反向边能到的所有点中，距离当前点最近且能改变它的连通性的点。~~又称最近的死神~~

这种点对于每个点来说都是有且仅有一个的，因为同时存在两个就意味着两个点都会影响也就意味着两个点其实根本不会影响它。

将这些点用有向边连起来。嘶，有基环树那味了。主要是很容易证出没环（点 $0$ 其实有个自环，但是由于不重要且影响最后的计算于是忽略了），那不就是一棵树吗？

至于怎么建这棵树，根据死神点的性质，一个点的父亲~~死神点~~其实就是它所有的入边的入点的最近公共死神祖先。那其实就好办了，开个 st 表动态维护即可。
```
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>G[N],G1[N],G2[N];
int dep[N],st[N][21],siz[N],rd[N];
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
	if(x==y)return x;
	for(int i=20;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
	return st[x][0];
}
void dfs(int x,int f)
{
	siz[x]=1;
	for(int y:G2[x])if(y!=f)
		dfs(y,x),siz[x]+=siz[y];
}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		while(cin>>x&&x)G[x].push_back(i),G1[i].push_back(x),rd[i]++;
	}
	for(int i=1;i<=n;i++)if(rd[i]==0)G[0].push_back(i),G1[i].push_back(0),rd[i]++;
	deque<int>q;q.push_back(0);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int y:G[x])
		{
			rd[y]--;
			if(rd[y]==0)q.push_back(y);
		}
		if(x==0)continue;
		int z=-1;
		for(int y:G1[x])
		{
			if(z==-1)z=y;
			else z=lca(z,y);
		}
		st[x][0]=z;dep[x]=dep[z]+1;
		for(int i=1;i<=20;i++)st[x][i]=st[st[x][i-1]][i-1];
		G2[z].push_back(x);
	}
	dfs(0,0);
	for(int i=1;i<=n;i++)cout<<siz[i]-1<<'\n';
	return 0;
}
```

ID

4480

时间

1000ms

内存

1024MiB

难度

标签

递交数

236

已通过

上传者

Hydro

6 条题解

P2597[灾难]

题目简述

题目分析

下面内容来自《中学生计算机程序设计提高篇》（有删减）

下面是自己的详细理解和对上面的补充

思路总结

易错点

代码实现

投诉

暴力

$\textcolor{#B0D628}{80}$ 分暴力代码

优化

什么样

怎么建

后续

$\textcolor{green}{AC}$ 代码

思路

AC代码

投诉

[ZJOI2012] 灾难

信息

状态

开发

支持

关于

6 条题解

P2597[灾难]

题目简述

题目分析

下面内容来自《中学生计算机程序设计提高篇》（有删减）

下面是自己的详细理解和对上面的补充

思路总结

易错点

代码实现

投诉

暴力

80\textcolor{#B0D628}{80}80 分暴力代码

优化

什么样

怎么建

后续

AC\textcolor{green}{AC}AC 代码

思路

AC代码

投诉

[ZJOI2012] 灾难

信息

状态

开发

支持

关于

还没有账户？

登录

$\textcolor{#B0D628}{80}$ 分暴力代码

$\textcolor{green}{AC}$ 代码