题目理解

有一棵 $n$ 个节点的树，每条边有边权。需要选择恰好 $k$ 个节点染成黑色，其余 $n-k$ 个节点染成白色。收益定义为：所有黑点对之间的距离和 + 所有白点对之间的距离和。

要求最大化这个收益值。

---

关键观察

1. 问题转化

原问题中直接计算所有点对距离和比较困难，但可以转化为计算每条边对总收益的贡献。

对于树中的一条边 $e$，设其权值为 $w$，它将树分成两个连通块，大小分别为 $size_a$ 和 $size_b$。

• 黑点对经过这条边的数量 = 左侧黑点数 × 右侧黑点数
• 白点对经过这条边的数量 = 左侧白点数 × 右侧白点数

因此，边 $e$ 对总收益的贡献为：

$$w \times \left( \text{黑左} \times \text{黑右} + \text{白左} \times \text{白右} \right) $$

2. 状态设计

考虑树形 DP：

• 令 $dp[u][i]$ 表示以 $u$ 为根的子树中，选择 $i$ 个节点染成黑色时，该子树能获得的最大收益（仅考虑子树内部的边）

3. 转移方程

对于节点 $u$ 和其子节点 $v$，连接边的权值为 $w$：

• 设 $v$ 的子树大小为 $sz_v$
• 设我们在 $v$ 的子树中选择 $j$ 个黑点（$0 \leq j \leq \min(k, sz_v)$）
• 则边 $(u,v)$ 的贡献为：

$$w \times \left[ j \times (k-j) + (sz_v - j) \times (n-k - (sz_v - j)) \right] $$

其中：

• $j \times (k-j)$：黑点对贡献（$v$ 子树中 $j$ 个，外部 $k-j$ 个）
• $(sz_v - j) \times (n-k - (sz_v - j))$：白点对贡献（$v$ 子树中 $sz_v - j$ 个白点，外部 $n-k - (sz_v - j)$ 个白点）

转移时使用背包合并：

$$dp[u][i] = \max\left( dp[u][i], \ dp[u][i-j] + dp[v][j] + \text{边贡献} \right) $$

---

算法设计

1. 预处理子树大小

通过一次 DFS 求出每个节点的子树大小 $size[u]$，便于后续计算。

2. 树形 DP + 背包

void dfs(int u, int fa) {
    size[u] = 1;
    dp[u][0] = dp[u][1] = 0;  // 初始化
    
    for (每条边 (u, v, w)) {
        if (v == fa) continue;
        dfs(v, u);
        
        // 背包合并
        for (int i = min(k, size[u]); i >= 0; i--) {
            for (int j = 0; j <= min(k, size[v]); j++) {
                if (dp[u][i-j] 无效) continue;
                
                int black_pairs = j * (k - j);
                int white_pairs = (size[v] - j) * (n - k - (size[v] - j));
                int edge_contribution = w * (black_pairs + white_pairs);
                
                dp[u][i] = max(dp[u][i], 
                              dp[u][i-j] + dp[v][j] + edge_contribution);
            }
        }
        size[u] += size[v];
    }
}

3. 最终答案

以任意节点为根（通常选择节点 1），答案即为 $dp[1][k]$。

---

算法正确性

1. 贡献分解的正确性

树中任意两点间的路径唯一，因此每条边对总距离和的贡献可以独立计算。将总收益分解为各边贡献之和是完备且不重不漏的。

2. 状态转移的完备性

• 树形 DP 遍历所有子树，考虑所有可能的黑点分配方案。
• 背包合并确保每个子节点的贡献只被计算一次。
• 边贡献的计算公式正确反映了该边对全局收益的影响。

3. 最优子结构

以 $u$ 为根的子树的最优解，可以由其子节点的最优解合并得到，满足动态规划的最优子结构性质。

---

复杂度分析

时间复杂度

• 每个节点都需要处理其所有子节点。
• 对于节点 $u$ 和子节点 $v$，需要枚举 $i$ 和 $j$。
• 最坏情况下，总时间复杂度为 $O(nk^2)$。
• 但由于树形背包的优化（$i$ 从大到小枚举，且不超过 $size[u]$），实际运行效率很高。
• 对于 $n \leq 2000, k \leq n$，完全可接受。

空间复杂度

• DP 数组：$O(nk)$
• 邻接表存储树：$O(n)$
• 总空间复杂度：$O(nk)$，在给定范围内可接受。

---

实现细节

1. 初始化

memset(dp, -1, sizeof dp);  // 初始化为无效值
dp[u][0] = dp[u][1] = 0;    // 合法状态

2. 边界条件

• 当 $k=0$ 或 $k=n$ 时，收益为所有点对距离和。
• 但算法能自然处理这些情况。

3. 枚举顺序

for (int i = min(k, size[u]); i >= 0; i--)  // 必须倒序，避免重复计算

---

算法标签

• 树形DP
• 复杂度分析
• 树结构
• 数论
• 欧拉定理
• 线段树

---

总结

本题通过巧妙的贡献转化，将看似复杂的点对距离和问题，转化为可独立计算的边贡献问题。利用树形 DP 配合背包合并，能够高效地求出最优解。关键在于理解每条边对总收益的贡献与两侧黑白点数量的关系，从而设计出正确的状态转移方程。