G. Tree Destruction 题解（树形 DP + 贪心）

这是一道经典树形 DP 题目，代码简洁、思路清晰，你的代码是标准满分解法。

一、题目回顾

给你一棵树，你可以删除一条路径（两个点之间的唯一路径）。 删除后，剩下的点会分成若干个连通块。 求：最多能分成多少个连通块。

二、核心观察（解题突破口）

1. 删除一条路径 = 切断所有伸出这条路径的子树

• 路径上的点全部删掉
• 每一个从路径伸出去的子树，都会变成一个独立连通块
• 答案 = 路径上所有点的「向外伸出的分支数量」之和

2. 最优策略

我们要选一条路径，使得这条路径上所有点的“出度贡献”之和最大。

三、DP 状态定义（最关键）

dp[u][0] = 子树 u 内部的最优答案（不经过 u）
dp[u][1] = 以 u 为一个端点的最优路径答案（单链）
dp[u][2] = 穿过 u 的最优路径答案（两条链拼成完整路径）

每个状态的含义

• dp[u][1]：选一条一端在 u 的路径，能获得的最大连通块数
• dp[u][2]：选一条穿过 u 的路径（从一个子树进来，从另一个子树出去），能获得的最大值
• dp[u][0]：子树内部的最优答案（不经过 u）

四、转移方程（代码核心）

1. 初始值

child = u 的儿子数量
dp[u][1] = dp[u][2] = child

• 每个点本身的贡献 = 它的儿子数（删掉这个点，会分裂出 child 个连通块）

2. 子树转移

// 子树内部最优
dp[u][0] = max(dp[v][0], max(dp[v][1], dp[v][2]) + 1);

// 单链最优：把儿子的链接上来
dp[u][1] = max(dp[u][1], dp[v][1] + child - 1);

// 双链最优：把两个儿子的链拼起来
dp[u][2] = max(dp[u][2], dp[u][1] + dp[v][1] - 1);

五、完整代码 + 逐行中文注释

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 10;

int t, n;
vector<int> G[MAXN];  // 树的邻接表
int dp[MAXN][3];      // DP 数组

inline int max(int a, int b) {
	return a > b ? a : b;
}

// DFS 求解树形 DP
void dfs(int u, int fa) {
	dp[u][0] = 0;       // 子树内部最优（不经过 u）
	int child = 0;      // 统计儿子数量

	// 计算 u 有多少个儿子
	for (auto v : G[u])
		if (v != fa) child++;

	// 初始值：每个点自己的贡献 = 儿子数量
	dp[u][1] = dp[u][2] = child;

	// 遍历所有儿子
	for (auto v : G[u]) {
		if (v == fa) continue;
		dfs(v, u);

		// 更新 dp0：子树内部最优
		dp[u][0] = max(dp[u][0], dp[v][0]);
		dp[u][0] = max(dp[u][0], max(dp[v][1], dp[v][2]) + 1);

		// 更新 dp2：把两个儿子的链拼成完整路径
		dp[u][2] = max(dp[u][2], dp[u][1] + dp[v][1] - 1);

		// 更新 dp1：把儿子的链接上来，形成更长的单链
		dp[u][1] = max(dp[u][1], dp[v][1] + child - 1);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while (t--) {
		cin >> n;
		// 清空邻接表
		for (int i = 1; i <= n; i++) G[i].clear();

		// 读入树边
		for (int i = 1; i < n; i++) {
			int u, v;
			cin >> u >> v;
			G[u].push_back(v);
			G[v].push_back(u);
		}

		// 特判 n=2
		if (n == 2) {
			cout << 1 << '\n';
			continue;
		}

		dfs(1, 0);
		// 答案是三种情况的最大值
		cout << max(dp[1][2], max(dp[1][0], dp[1][1])) << '\n';
	}
	return 0;
}

六、答案怎么来？

最终答案取三个值的最大值：

max(dp[root][0], dp[root][1], dp[root][2])

• dp[0]：最优路径在某棵子树内部
• dp[1]：最优路径是一条以根为端点的链
• dp[2]：最优路径是一条穿过根的链（两个子树之间）

七、复杂度分析

• DFS：$O(n)$
• 总复杂度：$O(\sum n)$
• 完美通过 $n \le 2 \times 10^5$

八、一句话总结

这道题的本质： 选择一条路径，最大化路径上所有点的“向外分支数”之和，用树形 DP 维护单链/双链/内部最优即可。