【补题】Codeforces Round 1000 (Div. 2) C. Remove Exactly Two_2063c - remove exactly two

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

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

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

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

代码：

#include 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 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> x >> y; ve[x].push_back(y); ve[y].push_back(x); a[x]++,a[y]++; } multiset 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 <> t;while (t--){solve();}}