P8882

gan1234 · 2022-12-15 18:18:35 · 题解

分析

首先我们要知道，一个图里连通块的数量是点数减去边数。

分析题目，每个非叶结点都从子结点中选取一个点 v 与之连接，也就是说有多少非叶结点就有多少条边。 我们令 x 为叶结点数量，那么 n-x 就是边的数量，连通块的数量就是 n-(n-x)，也就是 x。

我们发现叶结点有多少，连通块就有多少，题目就简化为求叶结点的数量。

做法

如何求叶结点数量？首先用一个变量，储存初始树的叶结点数量，再分别对于每个操作更新答案。

• Add 操作：如果 u 是非叶结点，叶结点数量加一，如果 u 是叶结点，叶结点总数不变。
• Del 操作：如果 u 的父结点是非叶结点，叶结点数量减一，如果 u 的父亲是叶结点，叶结点总数不变。
• Upd 操作：如果原来的根只有一个儿子，那么操作后就会变成叶结点，叶结点数就加一。如果新的根原来是叶结点，操作后叶结点数就减一。

因为要进行删边和访问父结点操作，所以可以用 set 来维护每个点的邻点。如果一个点只有一个邻点，那么这个点就是叶结点。叶结点的父结点就是唯一的邻点。

代码

最多 n+m 个点和删边 m 次，所以复杂度为 O(n+m\log(n+m))

#include<bits/stdc++.h>
using namespace std;
unordered_set<int>s[400005];
int n,m,rt=1;
int ans;
int f(int x){//判断是否是叶结点
    return (x==rt&&s[x].size()==0)||(x!=rt&&s[x].size()==1);
}
int main(){
    cin>>n;
    int x;
    for(int i=2;n>=i;i++){
        cin>>x;
        s[i].insert(x);s[x].insert(i);
    }
    for(int i=2;n>=i;i++)
        if(s[i].size()==1)ans++;
    cout<<ans<<endl;
    cin>>m;
    string str;
    for(int i=1;m>=i;i++){
        cin>>str>>x;
        if(str=="Add"){
            if(!f(x))ans++;
            s[x].insert(n+i);s[n+i].insert(x);
        }
        if(str=="Del"){
            s[*s[x].begin()].erase(x);
            if(!f(*s[x].begin()))ans--;
        }
        if(str=="Upd"){
            int y=rt;rt=0;
            if(f(x)&&!f(y))ans--;
            if(!f(x)&&f(y))ans++;
            rt=x;
        }
        cout<<ans<<endl;
    }
    return 0;
}