树形 DP
树形 DP 是在树结构上进行的动态规划，以节点为状态，利用树的递归性质，从叶子向上或从根向下进行状态转移。
一、树的直径
1.1 问题定义
树的直径是指树中任意两个节点之间最短路径的最大长度（路径上的边数）。直观理解就是树上最远的两个点之间的距离。
1.2 算法原理
两次 BFS（或 DFS）
- 从任意节点出发（比如 0），BFS 找到离它最远的节点
p。 - 从
p 出发，再次 BFS 找到离 p 最远的节点 q。
正确性证明：第一次 BFS 找到的端点一定是直径的一个端点，第二次 BFS 从该端点出发找到的另一个端点即为直径的另一端。该结论基于树的无环连通图性质。
1.3 实现
from collections import defaultdict
defbuild_tree(edges, n):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
return g
deftree_diameter(edges, n):
g = build_tree(edges, n)
defbfs(start):
dist = [-1] * n
q = [start]
dist[start] = 0
farthest = start
while q:
u = q.pop(0)
farthest = u
for v in g[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return farthest, dist
endpoint, _ = bfs(0) # 第一次 BFS
_, dist = bfs(endpoint) # 第二次 BFS
return max(dist) # 最大距离即为直径
1.4 例题一：求树的直径
题目描述
给定一棵包含 个节点（编号 到 ）的无根树，计算树的直径（边数）。
输入格式
样例输入 1（链状树）
5
0 1
1 2
2 3
3 4
输出：4
样例输入 2（星型树）
4
0 1
0 2
0 3
输出：2
代码调用
n = 5
edges = [(0,1),(1,2),(2,3),(3,4)]
ans = tree_diameter(edges, n)
print("树的直径为:", ans) # 输出 4
二、树的最大独立集
2.1 问题定义
在树中选择尽可能多的节点，使得任意两个被选的节点都不相邻，没有边直接相连。该集合称为最大独立集。
2.2 算法原理
采用树形 DP，后序遍历（DFS）。定义状态：
转移方程（设 是 的子节点）：
最终答案为 。
2.3 实现
defmax_independent_set(edges, n):
g = build_tree(edges, n)
dp = [[0, 0] for _ in range(n)]
visited = [False] * n
defdfs(u):
visited[u] = True
dp[u][1] = 1# 选择 u 自己
for v in g[u]:
if visited[v]:
continue
dfs(v)
dp[u][0] += max(dp[v][0], dp[v][1])
dp[u][1] += dp[v][0]
dfs(0) # 从任意根节点开始，这里选 0
return max(dp[0][0], dp[0][1])
2.4 例题二：最大独立集
题目描述
公司有 个员工（编号 到 ），关系树。邀请员工参加聚会，如果邀请某员工，则不能邀请其直接上级或直接下级。求最多能邀请多少人。
输入格式
- 接下来 行：每行两个整数 ，表示一条边（无向，代表上下级关系）
样例输入 1（链状）
3
0 1
1 2
输出：2（选 0 和 2）
样例输入 2（星型）
4
0 1
0 2
0 3
输出：3（选 1,2,3，不选 0）
代码调用
n = 4
edges = [(0,1),(0,2),(0,3)]
ans = max_independent_set(edges, n)
print("最大独立集大小为:", ans) # 输出 3
总结
拓展思考：
- 树的直径也可以用树形 DP 一次遍历求解，通过记录每个节点向下最长路径和次长路径。
- 最大独立集问题可以推广到一般图，会变为 NP-hard，但在树上有多项式解法。
- 若需要输出具体方案，可在 DP 过程中记录决策路径。
