题目
没有上司的舞会
这是一道非常经典的树形 DP（Tree DP）
这道题的难点不在于复杂的数学公式，而在于如何在一个树状结构中做决策。
解题思路
核心思路
我们可以把这棵树想象成一个真实的职场架构图。为了让快乐指数最大，对于每一个职员（节点 u），我们面临一个简单的二选一决策：
- 邀请 u 来参加舞会。
- 不邀请 u 来参加舞会。
这个决策之所以难，是因为它会产生连锁反应：
- 如果不邀请上司：那他的直接下属可以来，也可以不来（取决于下属怎么选更快乐）。
- 如果邀请上司：那他的直接下属绝对不能来。
状态定义
我们需要两个“平行宇宙”来记录每个职员在不同情况下的最大快乐值。定义数组 dp[u][0] 和 dp[u][1]：
dp[u][0]（上司没来）：表示以 u 为根的子树中，u 本人没来的情况下，能获得的最大快乐指数。dp[u][1]（上司来了）：表示以 u 为根的子树中，u 本人来了的情况下，能获得的最大快乐指数。
状态转移方程（决策逻辑）
我们采用从下往上（后序遍历）的方式，先搞定最底层的实习生，再搞定中层管理，最后搞定大 Boss。
假设当前职员是 u，他的下属是 v_1, v_2, \dots
情况一：u 来了 (dp[u][1])
-
自己的快乐：肯定包含 u 自己的快乐值 H_u。
-
下属的限制：因为 u 来了，所有下属 v 都被迫不能来。
-
公式：
dp[u][1] = H_u + \sum (dp[v][0])(我来了 = 我爽了 + 下属都没来的最大值)
情况二：u 没来 (dp[u][0])
-
自己的快乐：0。
-
下属的自由：因为 u 没来，下属 v 可以来，也可以不来。既然是为了快乐最大化，那就看下属哪种情况更强。
-
公式：
dp[u][0] = 0 + \sum (\max(dp[v][0], dp[v][1]))(我没来 = 0 + 每个下属最舒服的状态之和)
举例（基于样例）
我们还原一下样例的关系链：
1(1) 是 4(8) 的上司 -> 4 是 3(7) 的上司 -> 3 是 2(4), 6(3), 5(-6) 的上司。
第一步：处理底层（2, 5, 6）
- 2号(4): 来=4, 不来=0。
- 6号(3): 来=3, 不来=0。
- 5号(-6): 来=-6, 不来=0。
第二步：处理 3号(7)
- 3号来 (
dp[3][1])：- 自己(7) + 下属都没来(0 + 0 + 0) = 7。
- 3号不来 (
dp[3][0])：- 下属2：max(来4, 不来0) = 4
- 下属6：max(来3, 不来0) = 3
- 下属5：max(来-6, 不来0) = 0 （注意：如果下属来了倒扣分，不如不请他）
- 总和 = 4 + 3 + 0 = 7。
第三步：处理 4号(8)
- 4号来 (
dp[4][1])：- 自己(8) + 下属3不来(7) = 15。
- 4号不来 (
dp[4][0])：- 下属3：max(来7, 不来7) = 7。
- 总和 = 7。
第四步：处理 1号(1)
- 1号来 (
dp[1][1])：- 自己(1) + 下属4不来(7) = 8。
- 1号不来 (
dp[1][0])：- 下属4：max(来15, 不来7) = 15。
- 总和 = 15。
最终答案：max(1号来, 1号不来) = 15。
参考代码
import java.util.*;
public class Main {
// 邻接表存树：tree.get(u) 包含 u 的所有下属
static List<List<Integer>> tree = new ArrayList<>();
static int[] happy; // 快乐指数
static int[][] dp; // dp表
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
happy = new int[n + 1];
dp = new int[n + 1][2];
// 初始化邻接表
for (int i = 0; i <= n; i++) {
tree.add(new ArrayList<>());
}
// 读入快乐指数
for (int i = 1; i <= n; i++) {
happy[i] = sc.nextInt();
}
// 读入关系：a, b 表示 a 是 b 的下属 (b -> a)
for (int i = 0; i < n - 1; i++) {
int a = sc.nextInt(); // 下属
int k = sc.nextInt(); // 上司
tree.get(k).add(a); // 上司指向下属
}
// 从根节点开始树形DP
int root = 1;
dfs(root);
// 输出结果：根节点来或者不来的最大值
System.out.println(Math.max(dp[root][0], dp[root][1]));
}
// 递归函数（DFS后序遍历）
// 将 u 作为根节点的子树的快乐值计算出来
static void dfs(int u) {
// 初始化当前节点的状态
dp[u][1] = happy[u]; // 如果u来，初始值就是他自己的快乐值
dp[u][0] = 0; // 如果u不来，初始值为0
// 遍历所有下属（子节点）
for (int v : tree.get(u)) {
dfs(v); // 先递归解决下属的问题（这就叫后序遍历）
// 状态转移
// 1. u不来：下属 v 可以来，也可以不来，取最大值
dp[u][0] += Math.max(dp[v][0], dp[v][1]);
// 2. u来：下属 v 必须不来
dp[u][1] += dp[v][0];
}
}
}
总结
- 建树：用邻接表存储关系。
- DFS：从根开始递归，回溯时（计算完子节点后）更新父节点的状态。
- 方程：
- 来 = 自己 + \sum下属不来
- 不来 = \sum \max(下属来, 下属不来)
最长乘积链
这是树形 DP 中非常经典的**“换根 DP”**（或者叫“二次扫描法”）题目。
这道题的难点在于：对于任意一个点，它的“最长路径”来源有两个方向——来自子树（向下） 和 来自父节点（向上）。
解题思路
这就好比你要在全公司的所有员工中选一个“联络中心”。对于任何一个员工 u（联络中心），他都有若干个直接联系人（邻居）。
为了让乘积最大，我们需要找出从 u 出发的两条不同方向的最长“通讯线路”。
这些线路可能通向他的下属（子节点），也可能通向他的上司（父节点）。
核心难点
如果我们只看“下属”，一遍 DFS 递归就够了。但问题是，路径也可以往“上司”那边走。这就需要我们分别计算**“向下的最长路”和“向上的最长路”**。
算法步骤：两次 DFS
我们需要两次遍历来收集所有信息：
- 第一次 DFS（自底向上，汇报业绩）
每个节点收集其子树的信息。对于节点 u，我们需要知道：
- d1[u]：从 u 向下走能走的最长距离。
- d2[u]：从 u 向下走能走的第二长距离（必须来自不同的子节点）。
- 为什么要记录第二长？因为如果“向上的路”要经过某个孩子，我们就得用该节点的“第二长向下路”来更新那个孩子。
- 第二次 DFS（自顶向下，资源下发）
父节点把自己那边的最长链信息“推”给子节点。对于节点 u 的孩子 v：
-
v 往上看，能走的最长距离 up[v] 是多少？
-
这取决于父节点 u 的 up[u]（u 再往上走的距离）和 u 的其他孩子的最长链。
-
转移方程：
如果 v 是 u “最长向下路”上的那个孩子：
up[v] = weight(u,v) + \max(up[u], d2[u])(因为 v 不能回头走自己那条路，所以只能利用父亲的“第二长”向下路或者父亲的“向上路”)
否则：
up[v] = weight(u,v) + \max(up[u], d1[u]) -
统计答案
枚举每个点 u 作为“转折点”。如果不走回头路，它有三个主要延伸方向的数据：
- 向下的最长路 (d1[u])
- 向下的次长路 (d2[u])
- 向上的最长路 (up[u])
找出这三个数中最大的两个，相乘即可。
参考代码
import java.util.*;
public class Main {
// 使用邻接表存图，graph[u] 存储的是 int[]{v, w}，即 {目标点, 权重}
static List<List<int[]>> graph = new ArrayList<>();
// d1[u]: 从 u 出发，向下（子树方向）能走的最长路径长度
// d2[u]: 从 u 出发，向下（子树方向）能走的第二长路径长度（路径不能与 d1 重合）
static long[] d1, d2;
// p1[u]: 记录 d1[u] 这条最长路径具体是走向了哪一个子节点（用于后续判断路径冲突）
static int[] p1;
// up[u]: 从 u 出发，向上（父节点方向）能走的最长路径长度
static long[] up;
static long maxProduct = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
d1 = new long[n + 1];
d2 = new long[n + 1];
p1 = new int[n + 1];
up = new long[n + 1];
// 初始化邻接表
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
// 存边：int[]{邻居, 权重}
graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});
}
// 第一遍 DFS：自底向上
// 目的：计算每个节点“向下”能延伸多长 (d1, d2)
dfsDown(1, 0);
// 第二遍 DFS：自顶向下
// 目的：计算每个节点“向上”能延伸多长 (up)
dfsUp(1, 0);
// 统计答案
for (int i = 1; i <= n; i++) {
// 对于任意点 i，不回头的最长路径只可能来自三个方向：
// 1. 向下最长 (d1[i])
// 2. 向下第二长 (d2[i])
// 3. 向上最长 (up[i])
// 取这三个数中最大的两个相乘
long[] paths = {d1[i], d2[i], up[i]};
Arrays.sort(paths);
// 排序后 paths[1] 是次大，paths[2] 是最大
maxProduct = Math.max(maxProduct, paths[1] * paths[2]);
}
System.out.println(maxProduct);
}
/**
* 第一遍 DFS (自底向上)
* 作用：对于当前节点 u，收集所有子节点 v 的信息，计算出从 u 往“下”走的最长路径和次长路径。
* 逻辑：u 的最长路 = max(所有子节点 v 的最长路 + 边权 w)
*/
static void dfsDown(int u, int fa) {
for (int[] edge : graph.get(u)) {
int v = edge[0];
int w = edge[1];
if (v == fa) continue; // 也就是防止走回头路去父节点
dfsDown(v, u); // 递归先处理子节点
// 子节点 v 能够提供的路径长度
long currentLen = d1[v] + w;
// 更新 u 的最长和次长记录
if (currentLen > d1[u]) {
d2[u] = d1[u]; // 原来的老大变成老二
d1[u] = currentLen; // 更新老大
p1[u] = v; // 记录老大的来源（是哪个子节点贡献的）
} else if (currentLen > d2[u]) {
d2[u] = currentLen; // 更新老二
}
}
}
/**
* 第二遍 DFS (自顶向下)
* 作用：对于当前节点 u，将其“向上”的路径信息推送到子节点 v。
* 计算 up[v]，即 v 往上走到 u 之后，还能继续走多远。
* 逻辑：v 往上走只有两条路可选：
* 1. 走到 u 后，继续往上走 (利用 u 的 up 值)
* 2. 走到 u 后，转头向下走去 u 的其他分支 (利用 u 的 d1 或 d2)
*/
static void dfsUp(int u, int fa) {
for (int[] edge : graph.get(u)) {
int v = edge[0];
int w = edge[1];
if (v == fa) continue;
// 我们要计算 up[v]：v 往上(即往 u 的方向)能走的最长距离
// 这个距离 = edge(u, v) + (u 除了 v 这条分支外，能走的最长距离)
// 关键判断：u 除了 v 以外的最长路径是哪条？
long maxFromU;
if (p1[u] == v) {
// 情况 A：u 向下最长的路(d1)恰好是经过 v 的。
// 既然 v 往上走到了 u，它就不能回头再走回 v。
// 所以 u 只能给 v 提供“向下次长路(d2)”或者“向上最长路(up)”。
maxFromU = Math.max(up[u], d2[u]);
} else {
// 情况 B：u 向下最长的路(d1)不是经过 v 的（是经过别的兄弟节点的）。
// 那么 u 可以放心地把“向下最长路(d1)”提供给 v，或者“向上最长路(up)”。
maxFromU = Math.max(up[u], d1[u]);
}
up[v] = maxFromU + w;
// 既然算出了 v 的 up 值，就可以继续递归去更新 v 的子节点了
dfsUp(v, u);
}
}
}
总结
- 视角转换：不要只盯着“根节点”，树上的任意一点都可以看作是中心。
- 方向分解：以任意点为中心，路径无非就是“去孩子那边”或者“去父亲那边”。
- 二次扫描：
- 第一遍搞定“孩子那边”的数据。
- 第二遍搞定“父亲那边”的数据。
- 贪心策略：对于每个点，拿到所有方向的路径长度，取前两名相乘。
STA-station
这道题是 “换根 DP”（Re-rooting DP）的经典应用。
它的核心问题在于：如果我们用暴力法算出每一个点当根节点时的深度和，时间复杂度是 O(N^2)，对于 10^5 的数据量会超时。我们需要一种 O(N) 的方法，即只算一次根节点，然后通过公式推导出其他节点的答案。
解题思路
1. 暴力法的瓶颈
如果我们选定 1 号点为根，我们可以通过一次 DFS 算出所有点到 1 号点的深度之和。
当我们想求 2 号点为根的情况时，如果重新遍历全树，就会做大量重复计算。
2. 换根的本质：相邻节点的关系
想象你手里提着一串葡萄（树）。
- 当前你的手抓在节点 u 上（u 是根）。
- 现在你想把手移到 u 的子节点 v 上（让 v 变成根）。
在这个“换手”的过程中，树的形态发生了什么变化？
- v 的子树中的所有节点：离根节点（手）近了一步（深度全部 -1）。
- v 的子树以外的所有节点（包括 u 及其其他分支）：离根节点（手）远了一步（深度全部 +1）。
3. 推导状态转移方程
假设：
- f[u] 表示以 u 为根时，所有节点的深度之和。
- size[v] 表示以 v 为根的子树大小（节点个数）。
- n 是整棵树的节点总数。
当我们从父节点 u 换根到子节点 v 时：
- 减分部分：v 的子树内有 size[v] 个点，每个点深度 -1。贡献变化：-size[v]。
- 加分部分：剩下的点有 n - size[v] 个，每个点深度 +1。贡献变化：+(n - size[v])。
公式：
f[v] = f[u] - size[v] + (n - size[v])
简化后：
f[v] = f[u] + n - 2 \times size[v]
4. 算法流程
- 第一次 DFS（自底向上）：
- 默认以 1 为根。
- 计算出每个子树的大小
size[x]。 - 顺便算出以 1 为根时的初始深度和
dp[1]。
- 第二次 DFS（自顶向下）：
- 利用上面的公式，由父节点 u 的答案推导出子节点 v 的答案。
- 遍历过程中打擂台，记录最大值。
参考代码
import java.util.*;
import java.io.*;
public class Main {
// 邻接表存图
static List<List<Integer>> graph = new ArrayList<>();
// size[u]: 以 u 为根的子树大小
static int[] size;
// dp[u]: 以 u 为根时，所有节点的深度和
// 注意：深度和可能超过 int 范围，必须用 long
static long[] dp;
static int n;
static long maxDeepSum = -1;
static int ansNode = 1;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
size = new int[n + 1];
dp = new long[n + 1];
for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
graph.get(u).add(v);
graph.get(v).add(u);
}
// 第一次 DFS：初始化
// 1. 计算以1为根时，每个子树的 size
// 2. 暴力算出 dp[1] (以1为根的总深度和)
dfs1(1, 0, 0);
// 初始化答案（假设1号点最好）
maxDeepSum = dp[1];
ansNode = 1;
// 第二次 DFS：换根 DP
// 利用公式由父推子，遍历全树
dfs2(1, 0);
System.out.println(ansNode);
}
/**
* 第一次 DFS：初始化每个子树的 size
*
* @param u 当前节点
* @param fa 父节点
* @param depth 当前节点的深度（相对于节点1，根深度为0）
*/
static void dfs1(int u, int fa, int depth) {
size[u] = 1; // 每一个节点本身算1个大小
dp[1] += depth; // 累加到根节点1的总深度和中
for (int v : graph.get(u)) {
if (v == fa) continue;
dfs1(v, u, depth + 1);
size[u] += size[v]; // 累加子树大小
}
}
/**
* 第二次 DFS (换根)
*
* @param u 当前节点 (已经计算好 dp[u])
* @param fa 父节点
*/
static void dfs2(int u, int fa) {
// 尝试往子节点换根
for (int v : graph.get(u)) {
if (v == fa) continue;
// 核心状态转移方程：
// dp[v] = dp[u] - size[v] + (n - size[v])
// 解释：v的子树所有点距离减1，其他点距离加1
dp[v] = dp[u] - size[v] + (n - size[v]);
// 更新答案：题目要求最大值
// 如果数值相同，要求编号最小。
// 因为我们就按顺序遍历，只有 > 才更新，这样自然保留了同数值下较先遍历到的（或者加个判断）
if (dp[v] > maxDeepSum) {
maxDeepSum = dp[v];
ansNode = v;
} else if (dp[v] == maxDeepSum) {
ansNode = Math.min(ansNode, v);
}
// 继续向下递归，现在 v 成了父节点，去推导它的子节点
dfs2(v, u);
}
}
}
关键细节提醒
- 数据类型：N=10^5，如果退化成一条链，深度和大约是 1+2+...+10^5 \approx \frac{10^{10}}{2}，这超过了
int的范围（21亿，约 2 \times 10^9），所以dp数组和结果变量必须用long。 - 公式理解：记住口诀 “子树减，非子树加”。移向谁，谁的那一坨就变近了（减），剩下的一坨就变远了（加）。
二叉苹果树
这道题是 树形 DP 中最经典的模型之一，通常被称为 “树上背包” 或者 “有依赖的背包问题”。
这道题的难点在于：我们既要考虑树的连接性（必须要连着根），又要考虑数量限制（背包容量），还要在分叉口做资源分配（把 Q 个树枝分给左儿子多少？分给右儿子多少？）。
解题思路
题目本质
不要被“二叉树”、“剪枝”这些术语吓到。只用最直观的**“预算分配”逻辑来重新梳理这道题。这其实就是一个在树上分蛋糕**的问题。
这道题的本质是：
你是公司的CEO（根节点 1），手里拿着 Q 个编制（树枝数量）。
你有若干个部门经理（子节点），每个经理下面还有团队。
你需要决定：给每个经理分配几个编制？
- 如果不给编制，那这个经理连同他的整个团队都不能留（因为树枝断了）。
- 如果给编制，你必须先消耗 1个编制 把这个经理招进来（连接父子节点的边），剩下的编制再由这个经理在他的子树里继续分配。
- 目标：所有保留下来的员工（树枝）产出的总价值（苹果）最大。
状态定义（定义“账本”）
我们需要一个表格来记录每个节点在不同预算下的最大收益。
定义 dp[u][j]：
- 含义：在以 u 为根的子树中，如果我们一共只保留 j 条树枝，能得到的最多苹果数量。
- 初始状态：dp[u][0] = 0。不管 u 下面有多少苹果，如果一条树枝都不给，收益就是 0。
核心逻辑：分组背包（预算怎么分？）
假设当前节点 u 手里拿着总共 j 个编制，准备分给它的孩子 v。
这是一个典型的**“以此类推”**的过程：
- 我们先不管 v，假设 u 把这 j 个编制都分给了之前的孩子们（或者留着没用），此时的最大收益记录在 dp[u][j] 里。
- 现在，我们要考虑分一部分编制给 v，看看能不能让总收益变得更大。
分配方案
假设我们决定分给子树 v k 条树枝（k 是我们在 v 内部使用的树枝数）。
-
成本计算：
要在 v 的内部保留 k 条树枝，我们必须先连通 u 和 v。
所以，总共消耗的编制 = k + 1。
（其中 1 是连接 u \to v 的那根树枝，k 是 v 自己拿去分配的）。
-
收益计算：
总收益 = (u 剩下的编制能换来的收益) + (v 的 k 条树枝换来的收益) + (u-v 这根树枝的苹果)
NewValue = dp[u][j - (k + 1)] + dp[v][k] + w
限制条件
- j 是当前 u 的总预算，必须倒序遍历（就像 0/1 背包一样，防止重复利用资源）。
- k 是分给子树 v 的预算。显然 k + 1 不能超过 j，否则 u 就没那么多编制给 v 了。
状态转移方程（公式推导）
结合上面的逻辑，公式就非常清晰了：
对于节点 u 的每一个子节点 v（边权为 w）：
dp[u][j] = \max_{0 \le k < j} \Big( dp[u][j], \quad \underbrace{dp[u][j - k - 1]}_{\text{给其它子树留的}} + \underbrace{dp[v][k]}_{\text{v子树贡献的}} + \underbrace{w}_{\text{连接边贡献的}} \Big)
解读这个公式：
我们在做一个决策：要不要从 u 的总预算 j 中，切出来 k+1 份给 v？
- 如果不切（k不合法或者不选v），收益维持原判 dp[u][j]。
- 如果切，我们就看“剩下的钱能买到的最好的货”加上“新买的货”，是不是比原来更好。
为什么是“分组背包”？
可能有人会问：为什么这是分组背包？
- 物品组：每一个子节点 v 就是一个“物品组”。
- 物品：在这个组里，你可以选择“给 v 分配 0 条”、“给 v 分配 1 条”、“给 v 分配 2 条”... 这些不同的分配方案，相当于组里不同的“物品”。
- 互斥性：你只能从这个组里选一种分配方案（你不可能既给 v 1条，又给 v 3条）。
- 决策：我们在每个子节点（组）中选一个最优的 k（物品），放入 u 的背包（j）中。
执行流程总结
- DFS 深入：一直走到叶子节点。
- 计算子节点：算出叶子节点的 dp 表（其实都是 0，因为叶子没下属）。
- 回溯合并：回到父节点 u。
- 初始化 u 的 dp 表（仅考虑 u 自己的空壳）。
- 来了一个孩子 v：
- 枚举 u 的总预算 j（从大到小，比如从 Q 到 1）。
- 枚举给 v 的预算 k（从 0 到 j-1）。
- 用公式更新 dp[u][j]。
- 又来一个孩子：
- 在已经合并了 v 的基础上，继续枚举 j 和 k，把新孩子合并进去。
- 最终答案：dp[1][Q]。
这样理解，就把复杂的“树上依赖”变成了简单的“预算分配”问题了
参考代码
这里采用邻接表存图（虽然说是二叉树，但用通用树形 DP 写法适应性更强），并且直接在转移时加上边权，这样理解起来更直观（保留 j 根树枝）。
import java.util.*;
public class Main {
// 邻接表存图
// graph.get(u) 里的每一个 int[] 数组存储一条边：
// edge[0] = 目标节点 (v)
// edge[1] = 边的权重 (apples)
static List<List<int[]>> graph = new ArrayList<>();
// dp[u][j] 表示以 u 为根的子树，保留 j 条树枝的最大苹果数
static int[][] dp;
static int N, Q;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
Q = sc.nextInt();
// 初始化 DP 数组
dp = new int[N + 1][Q + 1];
// 初始化邻接表
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < N - 1; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int w = sc.nextInt();
// 存边：直接存 int 数组 {v, w}
graph.get(u).add(new int[]{v, w});
graph.get(v).add(new int[]{u, w});
}
// 从根节点 1 开始 DFS
// 初始时所有边都是 0 条
dfs(1, 0);
System.out.println(dp[1][Q]);
}
/**
* 树形 DP (分组背包模型)
* u: 当前节点
* fa: 父节点 (防止往回搜)
*/
static void dfs(int u, int fa) {
// 初始化：不管要多少树枝，如果不去连子节点，价值目前都是0
// dp[u][0] = 0 也就是默认值
// 遍历所有子节点（相当于遍历背包中的“物品组”）
for (int[] edge : graph.get(u)) {
int v = edge[0]; // 子节点编号
int w = edge[1]; // 连接 u-v 的树枝上的苹果数
if (v == fa) continue; // 不走回头路
// 1. 递归：先把子节点递归处理完，算出子节点的 dp 状态
dfs(v, u);
// 2. 状态转移：把子节点 v 合并到父节点 u 上
// 分组背包合并
// j: 当前要在 u 的子树中（包括 u 连接 v 的这条边）总共分配多少条树枝
// 必须倒序遍历 (从 Q 到 1)，防止同一个子节点被多次重复计算
for (int j = Q; j >= 1; j--) {
// k: 分配给子树 v 的树枝数
// k 从 0 开始，最大不能超过 j-1 (因为必须留 1 条边连接 u 和 v)
for (int k = 0; k <= j - 1; k++) {
// 状态转移方程：
// dp[u][j] = max(
// dp[u][j], // 不选这个子节点（或者保持原样）
// dp[u][j - k - 1] + dp[v][k] + w // 选这个子节点：u剩下的配额 + v分配的配额 + 连接边的苹果
// )
// 这里 dp[u][j - k - 1] 指的是“在处理 v 之前，u 已经分配好的最优解”
// dp[v][k] 是子节点的最优解
// w 是 u-v 这条边的苹果
dp[u][j] = Math.max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + w);
}
}
}
}
}
代码细节讲解
- 循环顺序：
dfs(v, u)必须在循环最开始，先把“子树背包”填满。for (int j = Q; j >= 1; j--)必须倒序。这是因为我们用的是一维数组（在dp[u]这一行上不断更新），如果正序遍历，可能会导致同一个子节点被多次累加（就像 0/1 背包变成了完全背包）。
k的范围：k代表子树v里保留的树枝数。j代表当前总预算。- 连接 u 和 v 必须消耗 1 条树枝。
- 所以子树
v最多只能分到j - 1条树枝。
- 时间复杂度：
- 粗略看是 O(N \cdot Q^2)。
- 因为 N, Q \le 100，计算量大约在 10^6 级别，对于 Java 1秒的时限来说非常安全。
总结
遇到“树上选 Q 个连通点/边求最值”的问题：
- 认准模型：这是“树上背包”。
- 设计状态：dp[u][j] 代表子树 u 选 j 个的代价/价值。
- 写好循环：
- 第一层：枚举子节点 v。
- 第二层：倒序枚举总容量 j（从大到小）。
- 第三层：枚举分给子节点的容量 k。
