题目描述
给定一棵树，根节点为1，每个节点都有权值，可以交换任意次任意相邻节点的权值，定义一棵树的美丽值为该树的所有子树的节点的权值和的总和，求美丽值最大值为多少?
输入
本题包含多组数据
第一行包含一个正整数T(1≤T≤1× 1e5）。
对于每组数据:
第一行包含一个正整数n(1 ≤n≤2 ×1e5) 。
接下来n-1行，每行包含两个整数u，v (1 ≤u,u≤n)，表示 u,v之间有一条无向边。
最后一行包含 n 个正整数a1, a2, a3,..., an (1≤ai≤1×1e5），表示每个节点的权值。
$\sum_{i=1}^T$ n≤2×105
第一行包含一个正整数T(1≤T≤1× 1e5）。
对于每组数据:
第一行包含一个正整数n(1 ≤n≤2 ×1e5) 。
接下来n-1行，每行包含两个整数u，v (1 ≤u,u≤n)，表示 u,v之间有一条无向边。
最后一行包含 n 个正整数a1, a2, a3,..., an (1≤ai≤1×1e5），表示每个节点的权值。
$\sum_{i=1}^T$ n≤2×105
输出
对于每组数据:
输出一行表示树的最大美丽值
输出一行表示树的最大美丽值
样例输入 Copy
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
样例输出 Copy
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
4
1 2
2 3
2 4
6 6 5 7
可以先交换节点2,3上的权值，再交换节点1,2上的权值此时的美丽值最大
该树的美丽值计算过程为:以1为根的子树权值和+以2为根的子树权值和+以3为根的子树权值和+以4为根的子树权值和=24+19+6+7=56