#include <bits/stdc++.h>

using namespace std;

char rr[1 << 22], *csy1, *csy2;
#define GC (csy1 == csy2 && (csy2 = (csy1 = rr) + fread(rr, 1, 1 << 22, stdin), csy1 == csy2) ? EOF : *csy1 ++)

template <class T>
inline void RI(T &t) {
    char c = GC;
    for (t = 0; c < 48 || c > 57; c = GC);
    for ( ; c > 47 && c < 58; c = GC) t = t * 10 + (c ^ 48);
}

const int MAX_N = 1000000 + 5;

int N, a[MAX_N], f[MAX_N][2], dep[MAX_N], ans;
struct Edge{
    int y, prev;
}e[MAX_N << 1];
int elast[MAX_N], ecnt;

void Build(int x, int y) {
    ecnt ++;
    e[ecnt].y = y;
    e[ecnt].prev = elast[x];
    elast[x] = ecnt;
}

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = a[u] + dep[u];
    f[u][1] = dep[u] - a[u];
    for (int i = elast[u]; i; i = e[i].prev) {
        int v = e[i].y;
        if (v != fa) {
            dfs(v, u);
            ans = min(ans, min(f[u][0] + f[v][1] - dep[u] * 2 + 1, f[u][1] + f[v][0] - dep[u] * 2 + 1));
            f[u][0] = min(f[u][0], f[v][0]);
            f[u][1] = min(f[u][1], f[v][1]);
        }
    }
}

void solve() {
    ecnt = 0;
    memset(elast, 0, sizeof(int) * (N + 1));
    
    RI(N);
    for (int i = 1; i <= N; i ++) RI(a[i]);
    for (int i = 1; i < N; i ++) {
        int x, y;
        RI(x); RI(y);
        Build(x, y); Build(y, x);
    }
    ans = 1;
    dfs(1, 0);
    printf("%d\n", ans);
}

int main() {
    int T;
    RI(T);
    while (T --) solve();
    return 0;
}