//// Divide Tree.cpp : 定义控制台应用程序的入口点。

////

//

//#include "stdafx.h"

//

//#include <stdio.h>

//#include <string.h>

//#include <cmath>

//#include <iostream>

//using namespace std;

//

//const int maxn = 10005;

//const int INF = 0x3f3f3f3f;

//

//int t, n, graph[maxn][maxn],weight[maxn],vis[maxn];

//int ans,sum[maxn];

//

//

////计算子树权值

////思路：沿着DFS路线就可以确定树的权值

//void sum_weight(int i)

//{

//    vis[i] = 1;

//

//    sum[i] = weight[i];

//

//    for (int j = 1; j <= n; j++)

//    {

//        if (!vis[j] && graph[i][j])//沿着边搜索没有经过的顶点

//        {

//            sum_weight(j);

//            sum[i] += sum[j];

//        }

//    }

//}

//

//

//

//void DFS(int i)

//{

//    vis[i] = 1;

//

//    for (int j = 1; j <= n; j++)

//    {

//        if (graph[i][j] && !vis[j])//也是沿着边搜索

//        {

//            //思路：

//            //1.一个顶点的权值：s[j]

//            //2.另一个顶点的权值:s[i] - s[j]

//            int sub_diff = (sum[i] - sum[j]) - sum[j];

//            ans = ans < abs(sub_diff) ? ans : abs(sub_diff);

//            DFS(j);

//        }

//    }

//}

//

//int main()

//{

//    scanf("%d",&t);

//    while (t--)

//    {

//        memset(graph, 0, sizeof(graph));

//        memset(vis, 0, sizeof(vis));

//        scanf("%d", &n);

//        for (int i = 1; i <= n; i++)

//        {

//            scanf("%d", &weight[i]);

//        }

//        for (int i = 1; i <= n-1; i++)

//        {

//            int v1, v2;

//            scanf("%d %d", &v1, &v2);

//            graph[v1][v2] = 1;

//            graph[v2][v1] = 1;//无向图！！！！

//        }

//

//        sum_weight(1);

//

//        ans = INF;

//        memset(vis, 0, sizeof(vis));

//        DFS(1);

//

//        printf("%d\n",ans);

//

//    }

//    return 0;

//}

//

#include "stdafx.h"

#include <stdio.h>

#include <iostream>

#include <cmath>

#include <vector>

#include <string.h>

using namespace std;

const int M = ;

const int INF = 0x3f3f3f3f;//c、c++的最大数是十六进制的0x

int t, n,ans,weight[M],vis[M],sum[M];

vector<int> G[M];

void sum_weight(int i)

{

    vis[i] = ;

    sum[i] = weight[i];

    for (int j = ; j < G[i].size(); j++)

    {

        int next = G[i][j];

        if (!vis[next])//沿着边搜索没有经过的顶点

        {

            sum_weight(next);

            sum[i] += sum[next];

        }

    }

}

void DFS(int i)

{

    vis[i] = ;

    for (int j = ; j < G[i].size(); j++)//直接遍历边比遍历顶点循环次数少，可以达到减枝的目的。

    {

        int next = G[i][j];

        if (!vis[next])//也是沿着边搜索

        {

            //思路：

            //1.一个顶点的权值：s[j]

            //2.另一个顶点的权值:s[i] - s[j]

            int sub_diff = (sum[] - sum[next]) - sum[next];//为什么这里是sum[1]-sum[j],不是sum[i]-sum[j]????

            ans = ans < abs(sub_diff) ? ans : abs(sub_diff);

            DFS(next);

        }

    }

}

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        memset(vis, , sizeof(vis));

        scanf("%d", &n);

        for (int i = ; i <= n; i++)

        {

            scanf("%d", &weight[i]);

            G[i].clear();

        }

        for (int i = ; i <= n - ; i++)

        {

            int v1, v2;

            scanf("%d %d", &v1, &v2);

            G[v1].push_back(v2);

            G[v2].push_back(v1);

        }

        sum_weight();

        ans = INF;

        memset(vis, , sizeof(vis));

        DFS();

        printf("%d\n", ans);

    }

    return ;

}