2023河南萌新联赛第五场郑州轻工业大学 J - 树上DP

时间限制C/C++ 1秒其他语言2秒
空间限制C/C++ 262144K其他语言524288K
64bit IO Format: %lld

题目描述

给定一棵树 根节点为 $1$每个节点都有权值可以交换任意次任意相邻节点的权值定义一棵树的美丽值为该树的所有子树的节点的权值和的总和求美丽值最大值为多少

输入描述:

本题包含多组数据

第一行包含一个正整数 $T$$1\le T\le 1\times 10^5$。

对于每组数据

第一行包含一个正整数 $n(1\le n\le 2\times 10^5)$ 。

接下来 $n-1$ 行每行包含两个整数 $u$$v$$1\le u,v\le n$表示 $u,v$ 之间有一条无向边。

最后一行包含 $n$ 个正整数a$a_1,a_2,a_3,...,a_n$$1\le a_i\le 1\times 10^5$表示每个节点的权值 。

${\sum }_{i=1}^{T}n\le 2\times 10^5$

输出描述:

对于每组数据

输出一行表示树的最大美丽值

示例1

输入

5
2
1 2
9 8
4
1 2
2 3
2 4
6 6 5 7
8
1 2
1 3
1 5
2 4
4 7
5 6
5 8
8 10 9 7 3 6 9 8
5
1 2
1 3
1 4
4 5
2 3 5 9 9
2
1 2
7 4

输出

26
56
163
63
18

说明

对于第二个样例
4
1 2
2 3
2 4
6 6 5 7
可以先交换节点2,3上的权值 再交换节点1,2上的权值
此时的美丽值最大
该树的美丽值计算过程为以1为根的子树权值和+以2为根的子树权值和+以3为根的子树权值和+以4为根的子树权值和=24+19+6+7=56

• 给定一棵根节点为 1 的树可以交换任意次任意相邻节点的权值求出该树的所有子树的节点的权值和的总和的最大值。
• 关键词贪心
• 对于每组数据输出一行表示树的最大美丽值
• 每个节点有多少个祖先节点表示该节点处在多少颗子树中由于其本身也是一棵子树的根意味着该节点对美丽值贡献次数为 (祖先的个数 + 1 ) 次。
• 每个节点有多少个祖先节点表示该节点处在多少颗子树中由于其本身也是一棵子树的根意味着该节点对美丽值贡献次数为 (祖先的个数 + 1 ) 次。
• 显然每个节点 u 对美丽值的贡献为 u 的深度次即 $de{p}_u\times a_u$ (默认根节点深度为 1)。
• 由于可以交换任意次任意相邻节点的权值所以这些权值可以在树上任意排列。
• 根据贪心可以尽量将较大的权值放在深度较大的节点即将权值和深度按非降序排序然后一一相乘的总和就是最大美丽值。

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

public class Main {
    static int N = 200010;
    static ArrayList<Integer>[] agj = new ArrayList[N];
    static int[] dep = new int[N];

    public static void dfs(int u, int fa) {
        dep[u] = dep[fa] + 1;
        for (int v : agj[u]) {
            if (v != fa) {
                dfs(v, u);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(bf.readLine());
            for (int i = 0; i <= n; i++) {
                agj[i] = new ArrayList<>();
            }
            for (int i = 1; i <= n - 1; i++) {
                String[] str = bf.readLine().split(" ");
                int u = Integer.parseInt(str[0]);
                int v = Integer.parseInt(str[1]);
                agj[u].add(v);
                agj[v].add(u);
            }
            String[] str = bf.readLine().split(" ");
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(str[i - 1]);
            }
            dfs(1, 0);
            Arrays.sort(a, 1, n + 1);
            Arrays.sort(dep, 1, n + 1);
            long res = 0L;
            for (int i = 1; i <= n; i++) {
                res += (long) a[i] * dep[i];
            }
            bw.write(res + "\n");
        }
        bw.close();
    }
}