题解 CF2063C Remove Exactly Two

cjh20090318 · 2025-01-23 09:41:22 · 题解

好吧我承认我是来水社区贡献的。

一道比较简单的题，年级里竟然还有同学无法战胜。

题意

你有一棵 n 个点的树，你需要执行以下操作刚好两次：

• 选择一个点 v。
• 断开和 v 相连的所有边，并删除点 v。

求经过操作后最多会有多少个连通块。

分析

考虑直接枚举每一个点，只需要找到另一个点断开以后能获得最大值。

这个断开的点会对它的子结点带来影响，度数减少了 1。

于是直接维护一个 std::multiset，暴力插入删除。

每条边只会被访问两次，所以时间复杂度 O(n \log n)。

虽然跑的很慢，效率不高，但是避免了分类讨论，编程复杂度相对较低。

代码

//the code is from chenjh
#include<bits/stdc++.h>
#define MAXN 200002
using namespace std;
int n;
vector<int> G[MAXN];
multiset<int> S;
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) G[i].clear();
    for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    S.clear();
    for(int i=1;i<=n;i++) S.insert(G[i].size());
    int ans=0;
    for(int i=1;i<=n;i++){
        S.erase(S.find(G[i].size()));//删去当前点。
        for(const int v:G[i]) S.erase(S.find(G[v].size())),S.insert(G[v].size()-1);
        ans=max(ans,(int)G[i].size()+*S.rbegin()-1);//取最大值。
        S.insert(G[i].size());
        for(const int v:G[i]) S.erase(S.find(G[v].size()-1)),S.insert(G[v].size());//撤销更改。
    }
    printf("%d\n",ans);
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}