小苯的树上操作

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

题目描述

小苯有一个 $n$ 个点 $n-1$ 条边的无向无根树，但其点权中可能存在负数。

现在如果树非空，则小苯可以对树进行一些“删点”操作任意次（两种都是任意次），具体的：

$\bullet$ 小苯可以选择任意一个度数至多为 $1$ 的节点，从树中直接删除该点和连接该点的边。
$\bullet$ 小苯可以选择任意一个度数恰好为 $2$ 的节点，从树中删除该点，并将该点连接的两个邻点连接起来。

小苯想知道，他最大可以将树的点权和变为多少，请你帮他算一算吧。
（注意：空树的点权视为 $0$ ）。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含若干行。
第一行一个正整数 ，表示两人所在树的点数。
第二行  个整数 ，表示每个点的点权。
接下来  行，每行两个正整数 ，表示  两点间有一条边相连。（保证输入是一棵树。）
（保证所有测试数据中  的总和不超过 。）

输出描述:

输出包含  行，对于每组测试数据，输出一行一个整数，表示小苯操作完后，树的最大点权和。

示例1

输入

复制

2
5
2 -3 -2 -4 4
1 2
1 3
2 4
2 5
7
-1 -1 -1 -1 -1 -1 1
1 2
2 3
3 4
4 5
5 6
6 7

输出

复制

6
1

说明

两个样例的树：