无权树中红-蓝节点配对的最短距离总和最小值求解咨询

核心思路：边贡献累加计算 #

树中两点的最短距离等于路径上的边数之和，要让总距离最小，本质是让每条边被配对路径经过的次数尽可能少。对于树中的任意一条边，切断它会将树分成两个子树，我们只需计算这条边在最优配对下的被经过次数，累加所有边的次数就是总最小距离。

具体实现步骤 #

• 先统计全局红节点总数N（题目中三种颜色节点数相同，因此蓝节点总数也为N）
• 用邻接表存储树结构，任选一个节点作为根节点，执行后序DFS遍历（先递归处理所有子节点，再处理当前节点）
• 遍历过程中，对每个子树统计两个值：
  • red_cnt：子树内红节点的数量
  • blue_cnt：子树内蓝节点的数量
    统计规则：当前节点若为红则red_cnt +=1，为蓝则blue_cnt +=1，再加上所有子节点返回的对应计数
• 对于当前子树与父节点连接的边，计算这条边的贡献：abs(red_cnt - blue_cnt)，将该值累加到总距离中
• 遍历完成后，累加的总和就是所求的最小总距离

关键说明 #

• 为什么这个思路正确？子树内红、蓝节点数的差值，就是必须跨这条边配对的节点数量——红多则多余的红要去外部找蓝，蓝多则多余的蓝要去外部找红，这是无法避免的最小跨边次数，保证了总距离最小
• 无需动态规划或记录未配对节点，时间复杂度为O(n)（n为节点总数），是最优解法
• 若用BFS实现，本质和DFS逻辑一致，只需按层次统计子树的红、蓝节点数即可，但DFS的递归实现更简洁

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