CF2063C Remove Exactly Two

前言

提供一个不需要分讨的 \(O(Tnlogn)\) 做法。

解题思路

首先会想到选出度数最大和次大的两个点删除。

但是注意到，有三个度数都为最大的点连在一起的时候，你不能先删中间的点。（可以随便举个例子手玩一下。）

这时有人就开始思考 dp 或者 分类讨论 了。

这时候想我这种没有思维的人就开始发力了。

假设要删的点为 \(x\) 和 \(y\)，并且先删 \(x\) 点。

直接暴力枚举每个点作为 \(x\)，并更新与之有连边的点的度数，再从剩下的点中选出度数最大的点计算答案，所有情况取最小值即可。

具体实现可以使用 multiset。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
vector<int> v[N];
void solve(){
    int n, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) a[i] = 0;
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        a[x]++, a[y]++;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    multiset<int> s;
    for(int i = 1; i <= n; i++) s.insert(a[i]);
    for(int i = 1; i <= n; i++){
        int sum = 1;
        s.erase(s.find(a[i]));
        for(int y : v[i]){
            s.erase(s.find(a[y]));
            s.insert(a[y] - 1);
        }
        sum += a[i] - 1;
        sum += *s.rbegin() - 1;
        for(int y : v[i]){
            s.erase(s.find(a[y] - 1));
            s.insert(a[y]);
        }
        s.insert(a[i]);
        ans = max(ans, sum);
    }
    cout << ans << endl;
    for(int i = 1; i <= n; i++) v[i].clear();
}
int main(){
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}