思路:贪心 + 树上dfs

考虑dfs,在自底向上的过程中记录子节点的权值和。

1.如果a[u] < s,至少让a[u] == s,所以ans += s - a[u]

2.如果a[u] >= s,那么u不需要增加权值就能满足条件

代码

java

import java.util.*;

class Main {
    static long ans = 0;  // 全局变量，用于存储最终的操作次数
    static long[] a;  // 数组 a 存储每个节点的权值
    static List<List<Integer>> edge;  // 邻接表表示树结构

    // 深度优先搜索函数
    static long dfs(int u, int p) {
        long s = 0;  // 记录子节点的权值和
        for (int v : edge.get(u)) {  // 遍历当前节点 u 的子节点
            if (v == p) continue;  // 跳过父节点，避免重复遍历
            s += dfs(v, u);  // 递归计算子树的权值和
        }

        // 如果当前节点的权值小于子树权值和
        if (a[u] < s) {
            ans += s - a[u];  // 增加操作次数
            a[u] = s;  // 更新当前节点权值为子树权值和
        }
        
        s += a[u];  // 将当前节点的权值加入到子树的权值和中
        return a[u];  // 返回完整子树的权值和
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();  // 输入节点数量
        a = new long[n];  // 初始化权值数组
        
        // 输入每个节点的权值
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        // 初始化邻接表
        edge = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            edge.add(new ArrayList<>());
        }

        // 输入树的边，建立树结构
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            edge.get(u).add(v);  // 添加无向边
            edge.get(v).add(u);  // 双向边
        }

        // 从根节点 0 开始dfs，p = -1 表示根节点没有父节点
        dfs(0, -1);

        // 输出最终的操作次数
        System.out.println(ans);
    }
}

python

'''
考虑dfs,在自底向上的过程中记录子树的权值和。

1. 如果a[u] < s,至少让a[u] == s,所以ans += s - a[u]
2. 如果a[u] >= s,那么u不需要增加权值就能满足条件
'''
n = int(input())  # 输入节点数量
a = list(map(int, input().split()))  # 输入每个节点的权值
edge = [[] for _ in range(n)]  # 邻接表初始化
for _ in range(n - 1):  # 输入边信息
    u, v = map(int, input().split())
    edge[u - 1].append(v - 1)  # 添加无向边
    edge[v - 1].append(u - 1)

ans = 0  # 全局变量存储操作次数

# 深度优先搜索函数
def dfs(u, p):
    global ans
    s = 0  # 记录子树的权值和
    for v in edge[u]:  # 遍历当前节点 u 的所有子节点
        if v == p:  # 跳过父节点，避免重复遍历
            continue
        s += dfs(v, u)  # 递归调用DFS，计算子节点的子树权值和
    if a[u] < s:  # 如果当前节点的权值小于子树的权值和
        ans += s - a[u]  # 增加操作次数
        a[u] = s  # 更新当前节点的权值为子树的权值和
    s += a[u]  # 将当前节点的权值加到子树权值和中
    return s  # 返回包含当前节点的完整子树权值和

# 从根节点（0）开始DFS遍历，p=-1表示无父节点
dfs(0, -1)
print(ans)  # 输出最终的操作次数

cpp

#include <iostream>
#include <vector>

using namespace std;
#define ll long long
ll ans = 0;  // 全局变量，用于存储操作次数
vector<ll> a;  // 数组存储每个节点的权值
vector<vector<int>> edge;  // 邻接表表示树结构

// 深度优先搜索函数
ll dfs(int u, int p) {
    ll s = 0;  // 子节点的权值和
    for (int v : edge[u]) {  // 遍历当前节点 u 的子节点
        if (v == p) continue;  // 跳过父节点，避免重复遍历
        s += dfs(v, u);  // 递归调用DFS，计算子树权值和
    }

    // 如果当前节点的权值小于子树权值和
    if (a[u] < s) {
        ans += s - a[u];  // 增加操作次数
        a[u] = s;  // 更新当前节点权值
    }

    s += a[u];  // 将当前节点的权值加到子树权值和中
    return a[u];  // 返回子树的完整权值和
}

int main() {
    int n;
    cin >> n;  // 输入节点数量

    a.resize(n);  // 初始化节点权值数组
    edge.resize(n);  // 初始化邻接表

    // 输入每个节点的权值
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 输入树的边，建立树结构
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // 转换为0-based索引
        edge[u].push_back(v);  // 添加无向边
        edge[v].push_back(u);  // 双向边
    }

    // 从根节点（0）开始DFS遍历，p=-1表示无父节点
    dfs(0, -1);

    // 输出最终的操作次数
    cout << ans << endl;
    
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红有一棵$n$个点的树，其中$1$号点是根。每个点有一个权值$a_i$。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。 小红每次操作可以选择一个点，将其权值加一。请问小红最少需要多少次操作，才能使这棵树变成一棵奇妙树。

输入描述

第一行一个整数$n$，表示树的节点数。

第二行n 个整数$a_i$;，表示每个点的权值。

接下来$n-1$行，每行两个整数$u$和$v$，表示$u$和$v$之间有一条边。

$2≤n≤10^5$

$1≤a_i≤10^9$

$1≤u,v≤n$

输出描述

输出一个整数，表示最少需要多少次操作。

样例1

输入

3
1 2 3
1 2
1 3

输出

4

说明

至少需要$4$次操作，将$1$号点的权值变为$5$.