思路：dp

给定一棵树，树上每个节点的丑陋值为节点深度乘节点丑陋值$a_i$，树的丑陋值为所有节点丑陋值的和。我们能够将一整棵子树裁剪下来，并给某一个节点当子树，求最小的树的丑陋值。

树的深度能够通过一次遍历得到结果，因此树的每个节点的丑陋值也能够在计算节点的深度时，通过递归计算出来。

为了让整棵树的丑陋值最小，一个很直观的想法就是，将裁剪出来的这棵子树嫁接到根节点，也就是1号节点下。

定义：$sum[i]$表示节点$i$及其子树的丑陋值的和(不乘深度)，$depth[i]$表示第$i$个节点的深度。

当我们选择一棵子树将其嫁接到1号节点下时，这个操作所带来的丑陋值的变化，就是$-(dp[i]-2)*sum[i]$。

这个公式的推导，可以先将其拆成两部分：$-dp[i]*sum[i]$与$2*sum[i]$，第一部分是这棵子树在原来深度时对整棵树的丑陋值所做出来的贡献，比如将一个深度为$4$的整棵子树嫁接到1号节点下，原来的深度$4$对其所有子节点都有$4*a[i]$的贡献，因此其总贡献就是$4*sum[i]$。那么$2*sum[i]$自然就是嫁接后，对整棵树丑陋值的贡献。

时间复杂度为$O(N)$

代码

C++

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 100005;
int n;
vector<int> e[MAX_N];       // 存储图的邻接关系
vector<long long> a(MAX_N); // 存储节点权值
vector<long long> depth(MAX_N); // 存储节点到根节点的距离
vector<long long> sum(MAX_N); // 存储以节点为根的子树的丑陋值和

// 深度优先搜索，计算节点距离和子树权值和
void DFS(int u, int fa) {
    sum[u] = a[u];
    for (int v : e[u]) {
        if (v != fa) {
            depth[v] = depth[u] + 1;
            DFS(v, u);
            sum[u] += sum[v];
        }
    }
}

int main() {
    cin >> n;

    for (int i = 0; i <= n; ++i) {
        e[i].clear();
        depth[i] = 0;
        sum[i] = 0;
    }

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

    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v); // 构建图的邻接关系
        e[v].push_back(u);
    }

    depth[1] = 1; // 根节点到根节点的距离为1
    DFS(1, 0); // 从根节点开始进行深度优先搜索，计算节点距离和子树权值和

    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        res += depth[i] * a[i]; // 计算总权值和
    }

    long long tmp = res;
    for (int i = 2; i <= n; ++i) {
        res = min(res, tmp - (depth[i] - 2) * sum[i]); // 更新最小权值和
    }

    cout << res << endl; // 输出最终结果
    return 0;
}

python

n = int(input())  # 输入节点数
e = [[] for _ in range(n + 1)]  # 邻接表
a = []  # 节点的丑陋值
dp = [0] * (n + 1)  # 深度
sum = [0] * (n + 1)  # 子树丑陋值之和

def DFS(u, fa):
    sum[u] = a[u]
    for v in e[u]:
        if v != fa:
            dp[v] = dp[u] + 1  # 计算深度
            DFS(v, u)
            sum[u] += sum[v]  # 计算每个子树的丑陋值之和

tmp = input().strip().split(" ")
a.append(0)
for i in tmp:
    a.append(int(i))

for i in range(1, n):
    u, v = map(int, input().split())
    e[u].append(v)  # 构建树的边
    e[v].append(u)
dp[1] = 1  # 初始化根节点深度为1
DFS(1, 0)  # 进行DFS遍历
res = 0  # 记录整棵树的丑陋值
for i in range(1, n + 1):
    res += dp[i] * a[i]
tmp = res
for i in range(2, n + 1):  # 尝试移动每棵子树
    res = min(res, tmp - (dp[i] - 2) * sum[i])
print(res)  # 输出结果

Java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n;
    static ArrayList<Integer>[] e;
    static long[] dp, sum, a;

    public static void DFS(int u, int fa) {
        sum[u] = a[u];
        for (int i = 0; i < e[u].size(); i++) {
            int v = e[u].get(i);
            if (v != fa) {
                dp[v] = dp[u] + 1; // 计算深度
                DFS(v, u);
                sum[u] += sum[v]; // 计算每个子树的丑陋值之和
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        e = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) e[i] = new ArrayList<>();
        a = new long[n + 1];
        dp = new long[n + 1];
        sum = new long[n + 1];

        for (int i = 1; i <= n; i++) a[i] = scanner.nextLong();
        for (int i = 1; i <= n - 1; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            e[u].add(v);
            e[v].add(u); // 输入
        }
        dp[1] = 1; // 初始化根节点深度为1
        DFS(1, 0); // 进行DFS遍历
        long res = 0; // 记录整棵树的丑陋值
        for (int i = 1; i <= n; i++) {
            res += dp[i] * a[i];
        }
        long tmp = res;
        for (int i = 2; i <= n; i++) { // 尝试移动每棵子树
            res = Math.min(res, tmp - (dp[i] - 2) * sum[i]);
        }
        System.out.println(res);
    }
}

题目描述

米小游是一名远近闻名的魔法师。

这天他受邀来到了一个国家，来帮这个国家的国王解决一个问题。这个国家的国王年轻时曾有一颗非常美丽的树，但是国王却不小心惹怒了一个十分邪恶的黑魔法师，于是黑魔法师施法，让这棵树变得十分丑陋。现在，这棵树一共有$n$个节点，根节点为$1$号节点，其深度为$1$。每个节点都被黑魔法师随机施加了一个丑陋值，丑陋值越大，越影响这棵树的美观度，影响值为该节点的深度乘其丑陋值。

国王苦苦寻找了半辈子解决方案，让无数魔法师尝试过，但都没办法将树变回原样。长时间受黑魔法影响，这棵树再也无法变为原样了。终于，国王找到了米小游，希望米小游能尽可能地将树的丑陋值减少，并承诺，减少了多少丑陋值，就给米小游多少钱。

米小游看了看树，发现受黑魔法影响，只能裁剪树的一部分将其嫁接到另一个节点上。米小游想挣尽可能多的钱，因此他想知道能将树的丑陋值降到的最小值是多少？

注：只能裁剪一次。

输入描述

第一行输入一个整数 $n(1 \leq n \leq 10^5)$表示的大小

第二行输入$n$个整数$a(1 \leq a_i \leq 10^8)$表示每个节点的丑陋值

接下来$n-1$行，每行输入两个整数$u,u(1 \leq u,u \leq n)$，表示树上的边

输出描述

输出一个整数表示最小的丑陋值.

样例

输入

4
3 2 1 4
1 2
1 3
3 4

输出

17