树形 DP：子树合并、连通选取与换根扫描

一、树形 DP 的拓扑依赖与物理本质

在基础的线性动态规划中，状态转移通常依托于一维序列或二维网格的单向推进。而在树形结构中，状态转移的顺序被树的拓扑层次严格限制。

核心逻辑：后序遍历与状态汇聚

树形结构天然具备递归分治的性质。在自底向上的子树合并中，节点 $u$ 的状态要等所有子节点 $v$ 的状态计算完毕后才能汇总。因此，树形 DP 通常依托深度优先搜索（DFS），在递归深入至叶子节点后，利用回溯的过程，自底向上完成状态的合并。

关键是“孩子先算”，不是非用递归不可。也可以像《树上路径处理》中的 BFS 序那样，先记录父亲与遍历顺序，再倒序汇总；这也是处理深链、避开递归栈限制的一条路。

树形 DP：后序遍历与状态汇聚

二、基础状态机：0/1 选取与子树裁剪

独立集 DP：选取状态与父子约束

1. 独立集模型与 0/1 状态转移 (洛谷 P1352 没有上司的舞会)

场景：给定一棵树，节点存在权值。求一个不存在直接父子关系的节点集合，使其权值和最大。

物理意义与推导：

引入第二维表示节点当前的选取状态。

$dp[u][0]$ ：表示在以 $u$ 为根的子树中，不选取节点 $u$ 时的最大权值。
$dp[u][1]$ ：表示在以 $u$ 为根的子树中，强制选取节点 $u$ 时的最大权值。

状态转移严格依据父子约束：

若选取父节点 $u$ ，则子节点 $v$ 强制处于不可选状态：

dp[u][1] = val[u] + \sum_{v \in son(u)} dp[v][0]

若不选取父节点 $u$ ，子节点 $v$ 的选取不受限制，各子树互不影响，选或不选取较大者：

dp[u][0] = \sum_{v \in son(u)} \max(dp[v][0], dp[v][1])

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6005;

vector<int> node[N];
int r[N],in[N],dp[N][2];

void dfs(int u){
	dp[u][0]=0;
	dp[u][1]=r[u];
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		dfs(v); // 先算完整棵子树，再把两种状态汇报给 u
		dp[u][0]+=max(dp[v][0],dp[v][1]);
		dp[u][1]+=dp[v][0]; // u 已选，直接孩子 v 不能选
	}
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>r[i];
	for(int i=1;i<n;i++){
		int l,k;
		cin>>l>>k;
		node[k].push_back(l);
		in[l]++;
	}
	int root=1;
	while(in[root]) root++;
	dfs(root);
	cout<<max(dp[root][0],dp[root][1])<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 连通性裁剪 (洛谷 P1122 最大子树和)

场景：树节点权值包含负数，求权值和最大的连通子树。

物理意义与推导：

定义 $dp[u]$ 为以 $u$ 为顶点的最大连通子树权值。

这里的“顶点”指选中部分里最靠上的节点。答案不一定经过整棵树的根，因此最后取所有 dp[u] 的最大值。

由于要求结构连通，父节点在合并子节点状态时，必须进行负权裁剪。若子节点 $v$ 汇报的 $dp[v] < 0$ ，将其接入当前连通块只会产生负贡献，必须舍弃。

dp[u] = val[u] + \sum_{v \in son(u)} \max(0, dp[v])

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=16005;

vector<int> node[N];
int a[N],dp[N];
int ans=-1e18;

void dfs(int u,int fa){
	dp[u]=a[u];
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i];
		if(v==fa) continue;
		dfs(v,u);
		if(dp[v]>0) dp[u]+=dp[v]; // 负贡献整枝舍弃，仍保持连通
	}
	ans=max(ans,dp[u]); // 最优连通块不一定经过整棵树的根
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		node[u].push_back(v);
		node[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

树形背包：子树分组与容量划拨

三、资源分配映射：树形背包模型

场景：在树上分配有限的资源（如保留限定数量的边或节点），且子节点的选取强依赖于父节点，求最优分配方案。(洛谷 P2015 二叉苹果树)

物理意义与推导：

树形背包是分组背包在树状拓扑上的直接映射。

全局资源总量 $Q$ 对应背包总容量。每个子树 $v$ 对应一个“物品组”，分配给该子树的资源量 $k$ 对应“组内物品”。

定义 $dp[u][j]$ 为以 $u$ 为根，分配 $j$ 个资源单位所获得的最大价值。

在二叉苹果树中，一个资源单位就是一条保留的边。给子树内部留 $k$ 条边，还要另外留出连接 u-v 的一条，所以另一部分剩下 j-k-1。

循环结构必须严格遵守分组背包的降维限制，以保证资源分配的互斥性：

枚举子树 $v$ （遍历物品组）。
倒序枚举父节点 $u$ 当前拥有的容量 $j$ 。
枚举划拨给子树 $v$ 的容量 $k$ 。

dp[u][j] = \max_{0 \le k < j}(dp[u][j], dp[u][j-k-1] + dp[v][k] + w(u,v))

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;

struct Edge{int v,w;};
vector<Edge> node[N];
int dp[N][N]; 
int n,q;

void dfs(int u,int fa){
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i].v;
		int w=node[u][i].w;
		if(v==fa) continue;
		dfs(v,u);
		for(int j=q;j>=1;j--){ // 倒序容量，防止同一棵子树被合并多次
			for(int k=0;k<j;k++){
				dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w); // -1 留给连接边 u-v
			}
		}
	}
}

void solve(){
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		node[v].push_back({u,w});
	}
	dfs(1,0);
	cout<<dp[1][q]<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

子树大小限容、选点与选边的换算、负权初始化，详见《树上背包》第五节。

换根 DP：两次扫描与状态平移

四、视角的降维打击：换根 DP (二次扫描法)

当题目要求“以树上任意节点为根时”的全局最优解，单次 DFS $O(N)$ 遍历全树会导致总复杂度上升至 $O(N^2)$ 。换根 DP 的核心是通过相邻节点间的拓扑关系，在 $O(1)$ 时间内完成状态的平移切换。

1. 核心模型：带权距离汇聚 (洛谷 P2986 Great Cow Gathering)

场景：树上每个节点存在点权（牛的数量），边存在边权（距离）。求选取一个最优节点，使所有点权汇聚至此的带权距离和最小。

物理意义与推导：

采用二次扫描（Two-pass DFS）策略。

第一阶段（自底向上）：选取任意节点（通常为 1 号）为根，统计出每个子树的点权和 $sz[u]$ ，并计算出以 1 号为汇聚点的初始总代价 $f[1]$ 。

f[1] = \sum_{v\ne 1} sz[v] \times w(fa[v],v)

这里要累加整棵树的每条父子边，不是只看根的直接儿子。每条边被它下方的牛各走一次，所以贡献就是子树牛数乘边长，代码中在每个节点回溯时累加即可。

第二阶段（自顶向下）：进行状态的推演切换。假设聚会点由节点 $u$ 转移至其子节点 $v$ 。

考察全局点权的相对位移：

位于 $v$ 子树内部的点权（共 $sz[v]$ ），距离聚会点缩短了 $w$ 的路程，产生负贡献 $-sz[v] \times w$ 。
位于 $v$ 子树外部的点权（共 $sum\_all - sz[v]$ ），距离聚会点增加了 $w$ 的路程，产生正贡献 $+(sum\_all - sz[v]) \times w$ 。

换根状态转移方程：

f[v] = f[u] - sz[v] \times w + (sum\_all - sz[v]) \times w

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

struct Edge{int v,w;};
vector<Edge> node[N];
int c[N],sz[N]; 
int f[N];       
int sum_all,ans=1e18;

void dfs1(int u,int fa){
	sz[u]=c[u];
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i].v;
		int w=node[u][i].w;
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		f[1]+=sz[v]*w; // 子树 v 中的牛到根 1 都要经过这条边
	}
}

void dfs2(int u,int fa){
	ans=min(ans,f[u]);
	for(int i=0;i<node[u].size();i++){
		int v=node[u][i].v;
		int w=node[u][i].w;
		if(v==fa) continue;
		f[v]=f[u]-sz[v]*w+(sum_all-sz[v])*w; // 子树内走近，子树外走远
		dfs2(v,u);
	}
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		sum_all+=c[i];
	}
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		node[v].push_back({u,w});
	}
	dfs1(1,0);
	dfs2(1,0);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

五、树上最小点覆盖与最大独立集的镜像对照（选学）

（先修要求：完全理解上文的 0/1 独立集模型）

场景：如果题目改成“选取最少的节点，使得树上的每一条边都至少有一个端点被选中”（最小点覆盖），状态该怎么转移？

这与最大独立集是经典的镜像问题。核心差异在于父子约束的严格程度。

在最大独立集中，要求“不能有相邻节点同时选中”，所以如果父节点 $u$ 不选，子节点 $v$ 可以选，也可以不选，比较这两种状态取最大值。

而在最小点覆盖中，要求“每一条边必须被覆盖”。考虑边 $u-v$ ：如果父节点 $u$ 不选，为了覆盖这条边，子节点 $v$ 必须强制选中，没有任何商量的余地！只有当父节点 $u$ 选中时，边 $u-v$ 已经被覆盖了，子节点 $v$ 才可以自由决定选或不选（比较两种状态取较小代价）。

物理推导与状态转移：设 $dp[u][0]$ 为不选 $u$ 时的最小覆盖代价， $dp[u][1]$ 为选中 $u$ 时的最小代价。

$u$ 不选， $v$ 必选： $dp[u][0] = \sum dp[v][1]$
$u$ 选中， $v$ 随意： $dp[u][1] = 1 + \sum \min(dp[v][0], dp[v][1])$

手算小例子：一条链 $A-B-C$ 。

独立集（求最大）：选 A、C（共 2 个），B 被空出。
点覆盖（求最小）：选 B（共 1 个），边 A-B 和 B-C 都被覆盖。改代码时别只改一个 max：初值应为 dp[u][0]=0, dp[u][1]=1；每个孩子算完后，执行 dp[u][0]+=dp[v][1] 和 dp[u][1]+=min(dp[v][0],dp[v][1])；最终答案取 min(dp[root][0],dp[root][1])。这里的 1 是“选中一个点”的代价，不再是舞会的幽默值。若题目给的是无根树，要双向建边，用 dfs(u,fa) 并跳过父亲，不能直接照搬舞会的单向上下级读入。

六、换根 DP 进阶：不可逆状态的前后缀合并排除法（选学）

在第四节的《Great Cow Gathering》中，我们在换根时做了一个减法：f[u] - sz[v]*w。这是因为“距离和”的合并操作是加法，加法是有逆运算的（减法）。我们把总和减去 $v$ 这根枝条的贡献，就干净利落地剥离了 $v$ 。

痛点：如果题目求的是“每个节点到树上最远节点的距离”呢？求最远距离，合并操作是 max。而 max 是没有逆运算的！你无法从 $\max(a, b, c)$ 中“减去” $b$ 从而还原出 $\max(a, c)$ 。

这就导致换根向下推演时，父节点 $u$ 想要把“除了 $v$ 之外的其他方向的最远距离”传递给 $v$ 时卡壳了。如果暴力遍历 $u$ 的所有其他孩子求 max，在菊花图（一个节点连着几万个孩子）的情况下，复杂度会当场退化到 $O(N^2)$ 。

1. 核心思想：把子节点“拍扁”做前后缀合并

为了在 $O(1)$ 时间内剔除某个特定孩子 $v$ 的信息，我们可以预处理出前缀最大值和后缀最大值。

假设 $u$ 有 4 个孩子： $v_1, v_2, v_3, v_4$ ，从 $u$ 经过各孩子向下走的最远距离分别是 $d_1, d_2, d_3, d_4$ （单位边权时即 down[v]+1）。
我们建立前缀数组 pref 和后缀数组 suff。
- pref[2] 存的是 $\max(d_1, d_2)$
- suff[4] 存的是 $\max(d_4, \dots)$
当我们要向 $v_3$ 换根时，要求“除了 $v_3$ 以外的最大值”，简直易如反掌：它就是 $\max(\text{pref}[2], \text{suff}[4])$ ！完美避开了 $v_3$ ，且查询只需 $O(1)$ 。

2. 完整实现：求每个节点的最远距离（自拟练习）

题目要求：给定一棵 $N$ 个节点的无根树（边权均为 1），求出每个节点到树上其他节点的最远距离。( $N \le 10^5$ )

同一问题也能用直径的两个端点求解，见《树的直径与重心》第八节“利用直径端点求每个点的最远距离”；这里保留前后缀合并法，练习不能直接做减法的换根状态。

算法分解：

down[u]：从 $u$ 向下走到其子树内部的最远距离（第一次 DFS 算出）。
up[u]：从 $u$ 向上走（经过父节点），再拐向其他分支的最远距离（第二次 DFS 换根算出）。
最终答案： $\max(\text{down}[u], \text{up}[u])$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

vector<int> node[N];
int down[N], up[N];

// 第一次扫描：求出向下的最远距离 down[u]
void dfs_down(int u, int fa) {
	down[u] = 0;
	for(int i = 0; i < node[u].size(); i++) {
		int v = node[u][i];
		if(v == fa) continue;
		dfs_down(v, u);
		down[u] = max(down[u], down[v] + 1);
	}
}

// 第二次扫描：换根，推导向上的最远距离 up[u]
void dfs_up(int u, int fa) {
	int deg = node[u].size();
	vector<int> pref(deg + 2, 0);
	vector<int> suff(deg + 2, 0);
	vector<int> val(deg + 2, 0);

	// 将孩子节点“拍扁”，先提取出每个方向的 down[v] + 1
	for(int i = 0; i < deg; i++) {
		int v = node[u][i];
		if(v == fa) val[i + 1] = 0; // 父节点方向的信息由 up[u] 单独提供
		else val[i + 1] = down[v] + 1;
	}

	// 构造前缀和后缀最大值
	for(int i = 1; i <= deg; i++) pref[i] = max(pref[i - 1], val[i]);
	for(int i = deg; i >= 1; i--) suff[i] = max(suff[i + 1], val[i]);

	// 正式向子节点传递 up 状态
	for(int i = 0; i < deg; i++) {
		int v = node[u][i];
		if(v == fa) continue;
		
		// v 的 up 信息来源：
		// 1. 经过 u 继续往上走 (up[u] + 1)
		// 2. 经过 u 拐入 u 的其他孩子分支 (前缀、后缀合并 + 1)
		int max_other_branch = max(pref[i], suff[i + 2]);
		up[v] = max(up[u], max_other_branch) + 1;
		
		dfs_up(v, u);
	}
}

void solve() {
	int n;
	if(!(cin >> n)) return;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		node[u].push_back(v);
		node[v].push_back(u);
	}
	
	dfs_down(1, 0);
	up[1] = 0; // 根节点没有向上的边
	dfs_up(1, 0);
	
	// 输出所有节点的最远距离
	for(int i = 1; i <= n; i++) {
		cout << max(down[i], up[i]) << (i == n ? "" : " ");
	}
	cout << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}
/*
样例输入:
5
1 2
1 3
2 4
2 5
样例输出:
2 2 3 3 3
*/