最优边权分配：树结构下最大化总通行费问题求解

嘿，这个问题其实核心是抓住树中每条边的贡献规律，结合排序不等式就能轻松解决。让我一步步给你拆解清楚：

问题核心分析 #

总通行费是所有城市对(i,j)（i<j）的路径通行费之和。换个角度看，每条边的通行费会被所有路径经过它的城市对累加，所以总通行费等于每条边的通行费 × 经过这条边的城市对数量的总和。我们的目标就是给每条边分配A中的值，让这个总和最大。

关键思路 #

1. 计算边的贡献系数：
   对于树中的任意一条边，当移除它时，树会被分割成两个节点数为k和m的子树（k + m = N+1，总共有N+1个城市）。那么经过这条边的城市对数量就是k×m——每个左边的节点和右边的节点配对，路径都会经过这条边。这个k×m就是这条边的贡献系数。

2. 最大化总和的技巧：
   根据排序不等式，要让乘积的总和最大，我们需要把数组A中最大的值分配给最大的贡献系数，次大的值分配给次大的系数，以此类推。简单说就是“大系数配大值，小系数配小值”。

具体实现步骤 #

1. 构建树结构 #

把输入的无向边转换成邻接表，方便后续遍历树。

2. 计算子树大小 #

从根节点1出发，用DFS或BFS遍历树，计算每个节点的子树大小（子树包含的节点总数）。对于连接父节点u和子节点v的边，它的贡献系数就是size[v] × (总节点数 - size[v])——因为移除这条边后，一边是size[v]个节点，另一边是总节点数减去size[v]个节点。

3. 排序并计算最大总和 #

• 把所有边的贡献系数收集起来，升序排序；
• 把数组A也升序排序；
• 从后往前遍历两个排序后的数组，将对应位置的元素相乘并累加，得到的结果就是最大总通行费。

代码实现（Python） #

因为N可以达到2×10^5，递归DFS会导致栈溢出，所以这里用迭代式的后序遍历计算子树大小：

import sys
from collections import deque

def main():
    # 快速读取输入，避免超时
    input = sys.stdin.read().split()
    ptr = 0
    N, _ = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    
    # 构建邻接表，城市编号1~N+1
    adj = [[] for _ in range(N + 2)]
    for _ in range(N):
        u = int(input[ptr])
        v = int(input[ptr + 1])
        adj[u].append(v)
        adj[v].append(u)
        ptr += 2
    
    A = list(map(int, input[ptr:ptr + N]))
    total_nodes = N + 1
    size = [1] * (total_nodes + 1)
    visited = [False] * (total_nodes + 1)
    
    # 迭代式后序遍历计算子树大小
    q = deque()
    q.append((1, -1))  # (当前节点, 父节点)
    
    while q:
        node, parent = q.pop()
        if visited[node]:
            # 处理节点：累加子节点的size
            for neighbor in adj[node]:
                if neighbor != parent:
                    size[node] += size[neighbor]
            continue
        visited[node] = True
        q.append((node, parent))
        # 先压入子节点（除父节点外），保证后序遍历顺序
        for neighbor in adj[node]:
            if neighbor != parent and not visited[neighbor]:
                q.append((neighbor, node))
    
    # 收集所有边的贡献系数（每个非根节点对应一条和父节点的边）
    coefficients = []
    for node in range(2, total_nodes + 1):
        coefficients.append(size[node] * (total_nodes - size[node]))
    
    # 排序后配对计算总和
    coefficients.sort()
    A.sort()
    
    max_toll = 0
    for c, a in zip(reversed(coefficients), reversed(A)):
        max_toll += c * a
    
    print(max_toll)

if __name__ == "__main__":
    main()

示例验证 #

拿题目中的示例输入来说：

• N=2，总节点数3；
• 边是1-3、2-3；
• 计算子树大小：节点2的size是1，节点3的size是2；
• 贡献系数数组是[1×(3-1)=2, 2×(3-2)=2]；
• A数组排序后是[5,7]；
• 总和是2×7 + 2×5 = 14 +10 =24，和示例输出一致。

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