Description

数据结构课上，老师发现了一种快速的出题方法，也就是可以利用仅仅一道题，不断进行修改迭代，产生新的题目。例如，题目x由题目y直接产生，用一条边(x,y)表示。由于练习时间有限，且x和y具有相似性，只需要练习x和y其中一道题目即可。现知每道题都对应一个收获指数，练习了某道题目x，则可获得x的收获指数。我们想要知道如何选择一些题目练习，使得具有相邻边的题目只练习其中一道，可以获得的最大的收获指数是多少？

Input

输入的第一行是一个整数T，表示一个有 T组数据。
每组数据首先输入n，表示有n道题目。
接下来的n行，对于这n行中的第i行，每行输入一个正整数a，表示第i道题目的收获指数。1<=i<=n, a>0
再接着的n-1行，每行输入两个代表题目编号的正整数x，y，表示x由y产生。

Output

输出一个数字，表示最大的收获指数。

提示：题目的关系可以构建一棵树

Sample Input

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

Sample Output

5