【补题】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();}
}