PART 0：说些闲话

写这题之前或之后不妨去写一写P1197 [JSOI2008]星球大战，这两题的思路都差不多，还有P1653 猴子，应该说这题三倍经验？

PART 1：思路简析

正题开始，按照题目的意思，我们需要对一个无向图进行删边，问每个点什么时候与 $1$ 号点不连通。但是在编程中，删边是很难的，加边是很容易的，于是我们换一个思路，考虑离线处理，先把所有要删的边先删掉，之后我们进行一次时光倒流，把每一条边加回去，这样问题就变成了，一个无向图，加入 $m$ 条边，问每个节点什么时候与 $1$ 号点相连。

这样问题就简单了，我们一条一条的把边加回去，对这条边未与 $1$ 号点相连的那一段进行 DFS，并记录答案

PART 2：时间复杂度

关于这个，本蒟蒻其实不太会证，但是照虎画猫，学着大佬的样子证一下，欢迎纠错。

由于每一个点只会经过一次 DFS 后就被标记掉，每一条边也只会遍历一次，所以时间复杂度应该是线性的，也就是 $O(n)$ 的，完全足以 A 掉这一题

PART 3：AC CODE

新鲜出炉的难看代码

#include<bits/stdc++.h>
#define MAXN 200010
#define MAXM 400010
using namespace std;
struct node{
	int l_son,r_son;
};
struct edge{
	int pre,to;
};
struct opearte{
	int id,hand;
};

int n,m,cnt,now_time=-1;
edge e[MAXN*4];
node monkey[MAXN];
opearte del[MAXM];
int ans[MAXN],head[MAXN];
bool is_alive[MAXN][2],vis[MAXN];

void add_edge(int u,int v){
	e[++cnt].pre=head[u];
	e[cnt].to=v; head[u]=cnt;
}
void dfs(int now){
	ans[now]=now_time;
	vis[now]=true;
	for(int i=head[now];i;i=e[i].pre){
		if(!vis[e[i].to]){
			dfs(e[i].to);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&monkey[i].l_son,&monkey[i].r_son);
		if(monkey[i].l_son!=-1) is_alive[i][0]=true;
        if(monkey[i].r_son!=-1) is_alive[i][1]=true;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&del[i].id,&del[i].hand);
        is_alive[del[i].id][del[i].hand-1]=false;
	}
	for(int i=1;i<=n;i++){
		if(is_alive[i][0]) add_edge(i,monkey[i].l_son),add_edge(monkey[i].l_son,i);
		if(is_alive[i][1]) add_edge(i,monkey[i].r_son),add_edge(monkey[i].r_son,i);
	}
	dfs(1);
	for(int i=m;i>=1;i--){
		now_time=i-1;
		int u,v;
		if(del[i].hand==1) u=del[i].id,v=monkey[del[i].id].l_son;
		else u=del[i].id,v=monkey[del[i].id].r_son;
		add_edge(u,v); add_edge(v,u);
		if(vis[u]&&!vis[v]) dfs(v);
		else if(vis[v]&&!vis[u]) dfs(u);
	}
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}