思路：贪心

一个点可以为一个连通块，每连接两个点，都会由两个连通块合并为一个连通块。

如果最开始将所有边都删除，则得到$n$个连通块，此时答案即为$v[n]$。之后每连接一条边，则连通块减少一个，要让得分最大，就需要连接最大的边。

对边进行排序后，从大到小扫描边并逆序更新答案即可。

代码

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve(){
    int n;
    cin >> n;  // 输入数组的大小
    vector<int> v(n + 1);  // 定义数组v，大小为n+1
    for (int i = 1; i <= n; i++) {
        cin >> v[i];  // 输入v数组的值
    }

    vector<int> w(n - 1);  // 定义数组w，大小为n-1
    for (int i = 0; i < n - 1; i++) {
        int u, v, val;
        cin >> u >> v >> val;  // 输入边的两个端点和权重
        w[i] = val;  // 将权重存入w数组
    }

    sort(w.begin(), w.end());  // 对w数组进行排序
    long long ans = v[n];  // 初始化ans为v数组的最后一个元素
    long long sum = 0;  // 初始化sum为0
    for (int i = n - 1; i > 0; i--) {
        sum += w[i - 1];  // 累加w数组中的元素到sum
        ans = max(ans, v[i] + sum);  // 更新ans为当前的最大值
    }

    cout << ans << endl;  // 输出结果
}

int main() {
    int t;
    cin >> t;  // 输入测试用例的数量
    while (t-- > 0) {  // 处理每个测试用例
        solve();
    }

    return 0;
}

Python

t=int(input())
while(t):
    t-=1
    n=int(input())
    g= {}
    v = list(map(int,input().split()))
    edge = []
    for i in range(n-1):
        a,b,w = map(int,input().split())
        edge.append(w)
    edge.sort()

    s = sum(edge)
    ps=[edge[0]]
    for i in range(1,n-1):
        ps.append(ps[i-1]+edge[i])

    mm = s+v[0]
    for i in range(n-1):
        mm = max(mm,s-ps[i]+v[i+1])
    print(mm)

Java

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());
        for(int _a = 0;_a < T;_a++){
            int n = Integer.parseInt(bf.readLine());
            int []a = new int[n];
            String []line = bf.readLine().split(" ");
            for(int i = 0;i<n;i++)a[i] = Integer.parseInt(line[i]);
            int []b = new int[n - 1];
            long sum = 0;
            long res = 0;
            for(int i = 0;i<n - 1;i++) {
                String []temp = bf.readLine().split(" ");
                b[i] = Integer.parseInt(temp[2]);
                sum += b[i];
            }
            Arrays.sort(b);
            res = sum + a[0];
            for(int i = 0;i<n - 1;i++){
                sum = sum - b[i];
                res = Math.max(res, sum + a[i + 1]);
            }
            System.out.println(res);
        }
    }
}

题目内容

小红有一题$n$个节点的树，树中每一条边都有一个权值，多多还有一个长度为$n$的正整数序列:$v_1,v_2,...,v_n$

删除树中若干条边之后(或者不删)，就会变成一个有$x$个连通块的图，此时的得分为：剩余边权和$+v_i$（两个可以互相到达的节点属于同一个连通块，注意一个孤点也是一个连通块）

小红可以删除图中若干条边（可以不删）。现在小红想知道，最多能够得到多少分。现在请你告诉小红答案。

输入描述

第一行一个整数$T$，接下来有$T$组数据

每组数据第一行一个整数$n(2≤n≤10^5)$

第二行$n$个整数$v_1,...v_n(1≤v_i≤10^9)$

接下来$n-1$行，每行$3$个数，$a,b,w(1≤a,b≤n,1≤w≤10^4)$。

表示节点$a$与节点$b$之间有一条权值为w的边

保证$\sum \limits n$ 不超过$10^5$

保证每组数据给定的都是一棵树

输出描述

对于每组数据输出一行一个整数，表示最多能够得到多少分

示例1

输入

1
3
1 3 4
1 2 1
2 3 2

输出

5

说明

删除1与2之间的边，此时剩余边权和=2，连通块数量=2，得分=2+v[2]=2+3=5

示例2

输入

2
3
3 3 4
1 2 1
2 3 2
3
1 2 5
1 2 1
2 3 2

输出

6
5

说明

第一组数据：不删除任何边

第二组数据：删除所有边

示例3

输入

1
5
2 5 2 1 4
2 1 1
2 4 4
4 3 3
1 5 4

输出

16

说明

删除2到1之间的边，形成2个连通块，此时得分为16