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

· · 题解

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;
}