无向树中指定节点子集两两配对后的最大距离总和如何计算

问题描述 #

给定一棵包含N个节点的无向树，共有N-1条权重为1的边，任意两个节点互相可达。现给定一个节点子集，要求将子集中的节点进行一一配对，求所有可行配对方案中，所有配对节点对的距离之和的最大值。

示例说明 #

输入：
节点总数N = 8
目标节点子集 = [2,4,5,6]
树结构如下：
   7
   |
6--1--2--8 
   | 
   3--4
   | 
   5

输出：最大距离和为6
可行最优配对：
(2,4) 路径为2-1-3-4，距离3
(6,5) 路径为6-1-3-5，距离3
总和 3+3=6

核心解法 #

这个问题不需要枚举所有配对方案，我们可以通过统计每条边的最大贡献来直接计算结果：

1. 首先记目标子集的总节点数为k（题目默认k为偶数，可以完成完全配对）
2. 对于树上任意一条边，删除这条边后树会拆成两个独立的连通块，记其中一个连通块内属于目标子集的节点数为cnt，另一个连通块内的子集节点数就是k - cnt
3. 要让总距离和最大，我们要尽可能让配对的两个节点分别在这条边的两侧：每有一对跨边的节点，这条边就会给总距离贡献1。这条边最多能贡献的次数就是min(cnt, k - cnt)，因为最多只能凑出这么多对跨边的配对
4. 把所有边的贡献累加，最终结果就是最大的总距离和

示例验证 #

我们用上面的示例验证计算逻辑：

• 子集总大小k=4
• 边1-2：删除后一侧有1个目标节点（2），另一侧有3个，贡献min(1,3)=1
• 边1-6：删除后一侧有1个目标节点（6），另一侧有3个，贡献min(1,3)=1
• 边1-3：删除后一侧有2个目标节点（4、5），另一侧有2个，贡献min(2,2)=2
• 边3-4：删除后一侧有1个目标节点（4），另一侧有3个，贡献min(1,3)=1
• 边3-5：删除后一侧有1个目标节点（5），另一侧有3个，贡献min(1,3)=1
• 其余边（1-7、2-8）删除后一侧没有目标节点，贡献0
  所有边贡献总和：1+1+2+1+1=6，和示例结果一致。

实现步骤 #

1. 用邻接表存储树的结构
2. 任选一个根节点，做一次后序DFS遍历，统计每个子树内属于目标子集的节点数
3. 遍历所有边，对每条边对应的子树统计值cnt，计算min(cnt, k - cnt)累加到总答案
   整体时间复杂度为O(N)，可以处理大规模的树结构。

内容的提问来源于stack exchange，提问作者Yash Gupta