树上背包
例题：[HAOI2015] 树上染色
题面描述
有一棵点数为 \(n\) 的树，树边有边权。给你一个在 \(0 \sim n\) 之内的正整数 \(k\) ，你要在这棵树中选择 \(k\) 个点，将其染成黑色，并将其他的 \(n-k\) 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。
做法
\(DP_{u, j}\) 表示以 \(u\) 节点为根的子树选取 \(j\) 个点染成黑色的最大值
那么我们的价值怎么算呢？
我们知道当前子树 \(u\) 内有 \(j\) 个点染成了黑色，那么另一个子树 \(v\) 它子树内一定是 \(k - j\) 个黑色的点。
而结果其实就是 \(u\) 子树内的黑点个数 \(\times\) \(v\) 子树内的黑点个数 \(+\) \(u\) 子树内的白点个数 \(\times\) \(v\) 子树内的白点个数
写出来就是
\[j \times (k - j) \times w + (size_v - j) \times (n - size_v - (k - j)) * w
\]
代码
void dfs(int u, int fa) {sz[u] = 1;for (auto X : g[u]) {int v = X.first, w = X.second;if (v == fa) continue;dfs(v, u);pre(i, min(sz[u], k), 0) pre(j, min(k, sz[v]), 0) dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j] + j * (k - j) * w + (sz[v] - j) * (n - sz[v] - (k - j)) * w);sz[u] += sz[v];}
}
换根DP
意义
简而言之就是给树换了个根，更方便求答案。
例题：P10962 Computer
题目描述
某学校在一段时间前购买了第一台计算机（因此这台计算机的编号是 1）。在最近几年中，学校又购买了 \(N-1\) 台新计算机。每台新计算机都连接到之前已经安装的计算机之一。学校的管理人员对网络运行缓慢感到担忧，想知道每台计算机需要发送信号的最大距离 \(S_i\)（即到最远计算机的电缆长度）。你需要提供这些信息。
形式化题意
给定一棵 \(n\) 个节点的树，求出每个节点到树中其他节点的最大距离。输出每个节点的最大距离。
解法
当以 \(1\) 为编号时，算出了所有的距离，你会发现有一部分可以重复使用。这，就是换根DP
剩下的DP定义就很简单了
代码
戳我看代码
vector<pii> g[N];
int dp1[N], dp2[N];void dfs1(int u, int fa) {for (auto X : g[u]) {int v = X.first, w = X.second;if (v == fa) continue;dfs1(v, u);int val = dp1[v] + w;if (dp1[u] < val) swap(dp1[u], val);if (dp2[u] < val) swap(dp2[u], val);}
}void dfs2(int u, int fa) {for (auto X : g[u]) {int v = X.first, w = X.second;if (v == fa) continue;int val = 0;if (dp1[v] + w == dp1[u]) val = dp2[u] + w; else val = dp1[u] + w;if (dp1[v] < val) swap(dp1[v], val);if (dp2[v] < val) swap(dp2[v], val);dfs2(v, u);}
}