树上DP
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

本题包含多组数据

第一行包含一个正整数 T（1\leq T \leq 1 \times 10^{5}）。

对于每组数据：

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

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

最后一行包含 n 个正整数a_1, a_2, a_3, ... , a_n（1 \leq a_i\leq1\times10^5），表示每个节点的权值 。

\sum_{i=1}^{T} n \leq 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