树形 dp
显然我们贪心的先执行第一种操作，最后再连边。
森林中不同棵树互不影响，所以考虑最小化每棵树的操作次数。考虑 dp。
我们要把一棵树分成若干条链，那么考虑每个子树 \(u\) 中，节点 \(u\) 的情况有三种：
- 执行了第一种操作，成为单独一个点。
- \(u\) 为链上的一个端点，显然不可能执行过第一次操作。
- \(u\) 不为链上的端点，显然不可能执行过第一次操作。
可以设 \(f_{u,0/1/2}\) 表示上面三种情况的最小操作次数。转移分类讨论，有：
\(f_{u,0}=\min(f_{v,0}-1,f_{v,2})+d_u+1\)，没有 \(f_{v,1}\) 转移的原因是 \(f_{v,1}>f_{v,2}\)。
\(f_{u,1}=\sum_{v}f_{v,0}-\max(f_{v,0}-f_{v,1})\)，这块求差值常用。
\(f_{u,2}=f_{u,1}-sec\)。
\(sec\) 表示 \(\max(f_{v,0}-f_{v,1})\) 的次大值。最后答案就是每个树的 \(\min(f_{u,0},f_{u,2})\) 加上连通块数量-1。
复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
int n, m, ans, sum, cnt = 1;
bool vis[N];
int d[N];
struct node {
int to, nxt;
} e[N << 1];
int h[N];
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
h[u] = cnt;
}
int f[N][3];
void dfs(int u, int fa) {
vis[u] = 1;
int mx = 0, sec = 0;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
int dt = f[v][0] - f[v][1];
if(dt > mx) sec = mx, mx = dt;
else if(dt > sec) sec = dt;
f[u][0] += std::min(f[v][0] - 1, f[v][2]);
f[u][1] += f[v][0];
}
f[u][0] += d[u] + 1;
f[u][1] -= mx;
f[u][2] = f[u][1] - sec;
}
void Solve() {
std::cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
std::cin >> u >> v;
add(u, v), add(v, u);
d[u]++, d[v]++;
}
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
sum++;
dfs(i, 0);
ans += std::min(f[i][0], f[i][2]);
}
std::cout << ans + sum - 1 << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}