题目描述

给定一棵以编号为1的节点为根节点的树，每个节点都有自己的权值

你需要删除若干条边，使得最终以编号为1根节点的树为一棵二叉树。

请问最终，这棵树上所有节点的权值之和最大是多少

格式

• 多组测试样例

输入格式

第一行是一个正整数$t(1 \le t \le 10^5)$,表示有t个测试样例

对于每一组测试

• 第一行是一个整数$n(1 \le n \le 2*10^5)$，表示树一共有$n$个节点

• 第二行有$n$个正整数$x_i,(1 \le x_i \le 10^9)$,代表第$i$个节点的权值

• 接下来$n-1$行，每行有两个整数$u,v(1 \le u \le n,1 \le v \le n)$，代表节点$u$和节点$v$之间有一条边

保证所有样例的$n$之和不大于$2*10^5$

输出格式

对于每一组测试 输出一个正整数，代表最终树的最大权值

样例

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

27
42
21