思路与方法
本题给定一棵以 1 号节点为根的无向树，每个节点有一个权值（可为负）。允许对任意非根节点进行两种删除操作：
- 删除度为 1 的非根叶子节点。
- 删除度为 2 的非根中间节点，并将其两个邻居直接连接。
操作任意次后，希望最大化剩余节点权值之和，且根节点 1 必须保留。
树上 DP 模型
题目内容
游游有一个 n 个点 n−1 条边的无向树，其中 1 号点为根节点，但其点权中可能存在负数。
现在如果树非空，则游游可以对树进行一些“删点”操作任意次(两种都是任意次)，具体的：
●游游可以选择任意一个度数恰好为 1 的非根节点，从树中直接删除该点和连接该点的边。
●游游可以选择任意一个度数恰好为 2 的非根节点，从树中删除该点，并将该点连接的两个邻点连接起来。
游游想知道，他最大可以将树的点权和变为多少，请你帮他算一算吧。
输入描述
每个测试文件内都包含多组测试数据。
第一行一个正整数 T(1≤T≤1000) ，表示测试数据的组数。
接下来对于每组测试数据，输入包含若干行。
第一行一个正整数 n(2≤n≤2×105) ，表示两人所在树的点数。
第二行 n 个整数 ai(−109≤ai≤109),表示每个点的点权。
接下来 n−1 行，每行两个正整数 u,v(1≤u,v≤n) ,表示 u,v 两点间有一条边相连。(保证输入是一棵树。)
(保证所有测试数据中n的总和不超过3×105.)
输出描述
输出包含 T 行，对于每组测试数据，输出一行一个整数表示游游操作完。
样例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
2
说明
两个样例的树如下图所示：
样例1：
样例2：
