https://codeforces.com/contest/2063/problem/C
题目大意
给出一棵 $n \ (2 \le n \le 2 \times 10^5)$ 个点的树，从中删掉 $2$ 个不同的点，问删完之后最多有多少个联通分量。
简要题解
首先 $n = 2, 3$ 是平凡的，单独处理就好。
其他情况，我们应该尽量删掉两个度最大的节点。但注意要处理两个点可能相邻的情况。
如果有 $3$ 个或以上度最大的节点，则至少有一对的是不相邻的，直接选这一对即可。
如果只有 $2$ 个，则这俩一定是最优的，但相邻的时候会少产生一个联通分量。
如果只有 $1$ 个，则我们还需要选取一个次大的点，尽量选一个不与最大点相邻的次大点。
复杂度
$T$：$O(n \log n)$ （log 来自于 set 也是可以去掉的。比如直接遍历所有次大点也行）。
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
int u, v;
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
cin >> u >> v; u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
if (n == 2) {
cout << "0\n";
return;
}
if (n == 3) {
cout << "1\n";
return;
}
vector<int> mxid, mx2id;
for (int i = 0; i < n; i++) {
if (mxid.empty()) {
mxid.push_back(i);
continue;
}
if (g[mxid[0]].size() == g[i].size()) {
mxid.push_back(i);
} else if (g[mxid[0]].size() < g[i].size()) {
mx2id = mxid;
mxid.clear();
mxid.push_back(i);
} else {
if (mx2id.empty()) {
mx2id.push_back(i);
} else if (g[mx2id[0]].size() < g[i].size()) {
mx2id.clear();
mx2id.push_back(i);
} else if (g[mx2id[0]].size() == g[i].size()) {
mx2id.push_back(i);
}
}
}
int ans = g[mxid[0]].size();
if ((int)mxid.size() > 2) {
ans += g[mxid[0]].size() - 1;
} else if ((int)mxid.size() == 2) {
ans += g[mxid[0]].size() - 1;
for (int v : g[mxid[0]]) {
if (v == mxid[1]) {
ans--;
break;
}
}
} else {
ans += g[mx2id[0]].size() - 1;
set<int> se;
int cnt = 0;
for (int i : mx2id) se.insert(i);
for (int v : g[mxid[0]]) {
if (se.count(v)) cnt++;
}
if (cnt == (int)mx2id.size()) {
ans--;
}
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Subsequence Update - Codeforces Round 1000 (Div. 2)