[CF2063C] Remove Exactly Two 题解

· · 题解

前言

CF 好题。

正文

题意：有一个无根树，移除 2 点之后联通分量的个数最大是多少。

以下皆钦定度数为入度和出度的和。

设节点 u 的度数为 \text{deg}_u，我们对依次移除的 2 点 i,j 进行分类讨论。

  1. 若 i,j 不相邻：

    断开 i 点，树显然会变成有 \text{deg}_i 个连通分量的图。

    断开 j 点，会再多出 \text{deg}_j-1 个联通分量。为什么呢？因为在刚刚断开的 \text{deg}_i 个分量里面必有 1 个包含 j （也包含其他的节点），断开 j 不会影响这一个连通分量，因此会少多出来 1 个连通分量。

    答案为 \text{deg}_i+\text{deg}_j-1。

  2. 若 i,j 相邻：

    与 (1) 同样的逻辑，断开 i 点，树还是会变成有 \text{deg}_i 个连通分量的图。

    但是，断开 j 点，我们会比刚刚再少多出来一个连通分量，因为移除 i 点的同时 j 点的度数也 -1 了。

    答案为 \text{deg}_i+\text{deg}_j-2。

问题来了，那怎么实现呢？

具体的，我们枚举点 i，然后根据上面的找出最大的满足条件的点 j。

注意到我们需要一个能实时排序，插入和移除的数据结构，我这里用的是 std::set 和 std::multiset。

具体实现细节看代码。

Code

时间复杂度显然为 \Theta(n \log n)。

#include <bits/stdc++.h>
#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,m,t,cnt=0;
const int maxn=2e5+10;
const double eps=1e-6;

int deg[maxn];
vector<int> e[maxn];
void solve(){
    int ans=0;
    cin>>n;
    fill(deg+1,deg+1+n,0);
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        deg[u]++,deg[v]++;
        e[u].pb(v);
        e[v].pb(u);
    }
    set<pair<int,int>> st;
    for(int i=1;i<=n;i++) st.insert(mkp(deg[i],i));
    for(int i=1;i<=n;i++){
        multiset<int> mt;
        st.erase(mkp(deg[i],i));
        for(int v:e[i]){mt.insert(deg[v]);st.erase(mkp(deg[v],v));}
        int case2=deg[i]+*prev(mt.end())-2;
        if(st.size()){
            int case1=deg[i]+(*prev(st.end())).first-1;
            ans=max({ans,case1,case2});
        }else{ans=max({ans,case2});}
        st.insert(mkp(deg[i],i));
        for(int v:e[i]) st.insert(mkp(deg[v],v));
    }
    cout<<ans<<endl;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>t;
    while(t--) solve();
    return 0;
}