P4773. 第4题-魔法树能量水晶分配
题目内容
多多家里生长着一棵巨大的魔法树。这裸树由 n 个魔法节点组成，节点之间通过 n−1 条能量脉络相连(保证整体是一棵无向连通树)
每个魔法节点都有一个“共鸣频率"，用一个整数数组 freq 表示。为了维持魔法树的运转，你需要给每个节点分配能量水晶。分配规则如下:
请你计算并返回，为了维持魔法树的运转，最少需要准备多少颗能量水晶？
输入描述
第一行包含一个整数 n(1<=n<=100,000)，表示魔法节点的数量。节点编号从 0 到 n−1。
第二行包含 n 个整数，第 i 个整数表示 freq[i](1<=freq[i]<=1000,000,000)。
接下来的 n−1 行，每行包含两个整数 u 和 v ，表示节点 u 和节点 v 之间有一条能量脉络直接相连。
输出描述
返回一个整数，表示最少需要的能量水晶总数。
补充说明
对于 60% 的数据，n<=1000;
对于 100% 的数据，n<=100,000;
样例1
输入
4
1 3 2 4
0 1
1 2
2 3
输出
6
说明
该树为一条直线:0(1)−1(3)−2(2)−3(4)
节点 0：1 颗
节点 2：1 颗
节点 1 (连着 0 和 2，频率最高)：需要比节点 0 和 2 都多，分配 2 颗
节点 3 (连着 2 ，频率比 2 高)：分配 2 颗
总计：1+2+1+2=6。
样例2
输入
5
5 1 1 1 1
0 1
0 2
0 3
0 4
输出
6
说明
节点 0 位于中心，频率为 5。周围 4 个叶子节点频率为 1。
4 个叶子节点各分配 1 颗水晶。
中心节点 0 频率高于所有相连节点，必须比它们都多，分配 2 颗。
总计 1∗4+2=6 颗。
