自动搬运

查看原文

来自洛谷，原作者为

	R_8x 你充Q币吗

搬运于2025-08-24 23:17:53，当前版本为作者最后更新于2025-06-12 10:32:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12749 [POI 2017 R2] 罢工 Strikes - 题解

题意简述：

给定一棵 $n$ 个节点的树和 $m$ 次操作，每次给出一个数 $x$，如果 $x$ 大于 $0$ 就删除节点 $x$ 和与它相连的所有边，否则将节点 $x$ 和与它相连的边添加回来（如果某一条边连接着 $x$ 和一个被删除的节点，则不添加这一条边），输出每次操作后的联通块数量，保证不会添加未被删除的节点或删除已被删除的节点。

思路:

乍一看可能没什么思路，一般情况下我们会使用并查集维护联通块数量，但这东西不能删节点，还需要 $O(n)$ 查询，不可取。所以，我们可以观察当删除节点 $x$ 后联通块数量的变化。

当删除节点 $x$ 时，假设 $x$ 是根节点，那么删除 $x$ 后，以 $x$ 的每一个未被删除的子节点为根的子树都会形成一个新的联通块，添加 $x$ 节点后则是减少相应数量个联通块，所以我们可以依次按题意模拟。

但是这样仍存在问题：怎样模拟？如果直接对边打标记，看似时间复杂度正确，实际上对于菊花图直接卡成 $n^2$，显然不行。由于把 $x$ 设为根节点会使树的形态变得不固定，所以我们可以钦定 $1$ 为根节点，然后维护每一个节点的父节点编号 $fa_i$ 和子节点数量 $son_i$，那么在删除节点 $x$ 时，在以 $x$ 为根的子树中新增的联通块数量为 $son_x -1$，同时要使 $son_{fa_x}$ 减少一，代表这个节点已被删除，不能形成新的联通块。如果 $fa_x$ 未被删除，那么与 $fa_x$ 相连的节点也会形成一个新的联通块，所以数量还需要加一。添加操作同理，只不过增加变为减少。虽然说的可能复杂，但代码并不长。

代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> mp[500005];
int n,ans=1,q;
int d[500005],fa[500005];
bool vis[500005];
void dfs(int u,int f)
{
	fa[u]=f;
	for(int v:mp[u])
		if(v!=f)
			d[u]++,dfs(v,u);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	vis[0]=1;//由于钦定1为根后，fa[1]为0，而0号节点不存在，所以打上标记，认为0一直是被删除的状态
	dfs(1,0);
	cin>>q;
	while(q--)
	{
		int x;
		cin>>x;
		if(x>0)
		{
			vis[x]=1;
			d[fa[x]]--;
			ans+=d[x]-1+(!vis[fa[x]]);
			
		}
		else
		{
			x=-x;
			vis[x]=0;
			d[fa[x]]++;
			ans-=d[x]-1+(!vis[fa[x]]);
		}
		cout<<ans<<"\n";
	}
	return 0;
}