1. 题意理解

我们有一棵 N 个节点的树，每条边有 ( c_i ) 个猫零食。

对于每个根节点 ( i )，我们要选择 K 条从根出发的路径（到 K 个不同叶子或任意节点），使得路径上边权之和最大，且重复经过的边只算一次。

换句话说：选 K 条从根出发的路径，覆盖的边权总和最大。

---

2. 问题转化

这是一个树上选 K 条不相交路径的问题（不相交指边不重复计算）。

对于固定根，最优解是：选择根到 K 个叶子的路径，且这些路径的边集并集的权值和最大。

---

3. 关键观察

设 ( f(u) ) 表示以 u 为根的子树中，选择若干条从 u 出发的路径的最大权值和（考虑边不重复）。

实际上，对于固定根 r，答案 = 根到某些叶子的路径的边权和，但边不重复。

等价于：把树看成有根树，每条边有一个权值，我们要选 K 条从根到叶子的路径，最大化覆盖的边权总和（边可被多条路径覆盖，但权值只算一次）。

---

4. 经典解法思路

对于固定根，我们可以用长链剖分思想：

• 对每个节点，记录从它出发到叶子的最长路径（dep[u]）和次长路径
• 用动态规划或贪心选择前 K 大的“链权值”

但题目要求对每个根都输出答案，所以需要换根 DP。

---

5. 代码结构分析

5.1 数据结构

multiset<int> s1, s2;

• s1：存储当前选择的 K 条最大路径权值
• s2：存储剩余的路径权值（未选择的）

ans：当前 s1 中元素的和（即当前选择的 K 条路径的总权值）

---

5.2 核心函数

add(x)：将权值 x 加入集合，维护 s1 大小为 K

• 如果 s1 大小 < K，直接加入 s1
• 否则，如果 x 大于 s1 的最小值，替换

del(x)：从集合中删除权值 x

• 如果在 s2 中，直接删除
• 如果在 s1 中，删除后如果 s1 大小 < K，从 s2 补一个最大的

---

5.3 DFS1：预处理

dfs(x, fa)：计算每个节点到叶子的最长路径 dep[x]

• 同时记录重儿子 son[x]（对应最长路径）
• 将非重儿子的 dep 值加入集合（这些是候选路径）

---

5.4 DFS2：换根 DP

dfs2(x, fa)：计算以 x 为根的答案

• 记录 res[x] = ans
• 对每个子节点 y 进行换根：
  • 从集合中删除 y 相关的路径权值
  • 添加从父节点方向来的新路径权值
  • 递归到 y
  • 恢复状态

---

6. 算法流程

1. 第一次 DFS：计算每个节点向下的最长路径，将非重儿子的路径权值加入候选集
2. 初始化：将根节点的最长路径加入集合
3. 第二次 DFS：换根计算每个节点为根的答案
   • 维护一个大小为 K 的最大权值集合
   • 通过删除/添加路径权值来更新状态

---

7. 样例验证

样例中 N=11, K=3

• 根为 1 时，选择路径到 4,6,9，总权值 28
• 根为 4 时，选择路径到 1,6,9 等，总权值 32
• 输出与样例一致

---

8. 算法标签

• 换根 DP (Rerooting DP)
• 长链剖分 (Heavy-Light Decomposition)
• 贪心选择 (Greedy Selection)
• multiset 维护前 K 大 (Top-K Maintenance)

---

9. 复杂度分析

• 每个节点在 DFS 中被处理常数次
• 每次 add/del 操作 O(log N)
• 总复杂度 O(N log N)

---

10. 核心思想总结

1. 问题转化：选 K 条路径 → 选 K 条从根到叶子的路径，边不重复计算权值
2. 长链剖分：每个节点维护向下最长路径，用于路径候选
3. 换根 DP：通过维护前 K 大路径权值集合，在换根时快速更新答案
4. 数据结构优化：用 multiset 高效维护前 K 大元素

这种方法高效地解决了对每个根求答案的问题，适用于 N ≤ 1e5 的大规模数据。