【补题】Codeforces Round 1000 (Div. 2) C. Remove Exactly Two

题意：给一个树，可以从里面删去两个点，使连通块数量最大

思路：题解：CF2063C Remove Exactly Two - 洛谷专栏

这道题很容易想到，直接删去度最多的两个点就行了，但是这并不对，因为相邻点被删去之后，会导致自己的度数-1，所以删去的第一个点和第二点都要好好考虑，本人就是没考虑第一个点对第二个点的影响，第一个点选择错了，可能第二点永远选不出最佳，反例就是三个度相同的点在一起，你不能选中间那个

因此转换思路，第一个点不贪心选，而是暴力枚举，第二个点贪心选择即可，不能两个点都贪心选，是不正确的，连通块可以直接计算得到，也好想

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                       \
	std::ios::sync_with_stdio(0); \
	std::cin.tie(0);              \
	std::cout.tie(0)

const int N = 3e5 + 5;
const int INF = 1e18;
const int MOD = 998244353;
// const int MOD=1e9+7;
// const int MOD=100003;
const int maxn=5e5+10;

std::vector<int> ve[N];
int a[N];

void solve(){
    int n;
    std::cin >> n;
    
    for(int i=1;i<=n;i++){
        a[i]=0;
        ve[i].clear();
    }
    for(int i=0;i<n-1;i++){
        int x,y;
        std::cin >> x >> y;
        ve[x].push_back(y);
        ve[y].push_back(x);
        a[x]++,a[y]++;
    }

    multiset<int> se;
    for(int i=1;i<=n;i++){
        se.insert(a[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        int sum=1;
        se.erase(se.find(a[i]));
        for(auto v : ve[i]){
            se.erase(se.find(a[v]));
            se.insert(a[v]-1);
        }
        sum+=a[i]-1;
        sum+=*se.rbegin()-1;
        for(auto v : ve[i]){
            se.erase(se.find(a[v]-1));
            se.insert(a[v]);
        }
        se.insert(a[i]);
        ans=std::max(sum,ans);
    }
    std::cout << ans << '\n';
    

}

signed main()
{
	IOS;

	int t = 1;
	std::cin >> t;
	while (t--)
	{
		solve();
	}
}