最优边缘权值

Question

有一个州（地区），它是根植于节点1的树。该州所有城市（编号从1到N+1)都是通过双向道路连接起来的。你得在每条路上加通行费税。该州有N条公路连接各城市。您必须在道路上分配通行费税，以便最大限度地实现以下所述的功能通行费：

for(i=1;i<=number of cities;i++)
{
    for(j=i+1;j<=number of cities;j++)
    {
        toll+=(toll required to pay to travel from i to j)
     } 
}

你得把通行费税最大化。根据给定数组A中的通行费税分配道路（每个值只使用一次）。查找获得的最大通行费。

输入格式：

第一行包含

N和一个值始终为2的整数。

那么,

接下来的N条道路包含2个整数u和v，表示道路所在的城市。

下一行包含N个空格分隔的值，表示数组A的元素。

输出格式

打印可获得的最大通行费。

输入约束

1≤N≤2∗10^5

1≤A[i]≤1000
1≤u,v≤N+1

样本输入

2 2

1 3

2 3

5 7

样本输出

24

说明将5分配给边(1-3)，将7分配给边（2-3）。这导致通行费税最高为24。

Answer 1

首先，当您查看toll函数代码和示例输入时，您将看到该函数只计算路径：

• 从1到3
• 从2到3
• 但不是3到1
• 而不是3到2，

因为j总是大于i，所以这导致24是不正确的答案（或者您有不正确的toll)函数。

其次，根据这个任务（但我相信它只是描述错了），答案总是等于数组A的元素之和，因为这个任务听起来像是：将元素放入一个对称矩阵，然后在对角线上方（或下方）计算一个和，但它将是数组A的所有相同元素。