#include <bits/stdc++.h>

using namespace std;

const int SIZE = 1000000 + 5;
const int INF = 1e9;

int getInt(void) {
    int ch = getchar(), res = 0;
    while (!isdigit(ch)) {
        ch = getchar();
    }
    for (; isdigit(ch); ch = getchar()) {
        res = res * 10 + (ch - '0');
    }
    return res;
}

int n;
int li[SIZE];
int dep[SIZE];
int tick, dfn[SIZE], post[SIZE], bel[SIZE];
vector<int> out[SIZE];

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    dfn[u] = ++tick;
    bel[tick] = u;
    for (int v : out[u]) {
        if (v != fa) {
            dfs(v, u);
        }
    }
    post[u] = tick;
}

struct SegTree {
    static const int SGSZ = SIZE << 2;

    int nd[SGSZ], tag[SGSZ];

    void pushUp(int p) {
        int lc = p << 1, rc = lc | 1;
        nd[p] = min(nd[lc], nd[rc]);
    }

    void init(int p, int nle, int nri) {
        tag[p] = 0;
        if (nle == nri) {
            int u = bel[nle];
            nd[p] = dep[u] - li[u];
            return;
        }
        int mid = (nle + nri) >> 1, lc = p << 1, rc = lc | 1;
        init(lc, nle, mid);
        init(rc, mid + 1, nri);
        pushUp(p);
    }

    void tagOn(int p, int t) {
        nd[p] += t;
        tag[p] += t;
    }

    void pushDown(int p) {
        int lc = p << 1, rc = lc | 1;
        tagOn(lc, tag[p]);
        tagOn(rc, tag[p]);
        tag[p] = 0;
    }

    void mdf(int p, int nle, int nri, int le, int ri, int v) {
        if (le > ri) {
            return;
        }
        if (nle == le && nri == ri) {
            tagOn(p, v);
            return;
        }
        pushDown(p);
        int mid = (nle + nri) >> 1, lc = p << 1, rc = lc | 1;
        if (ri <= mid) {
            mdf(lc, nle, mid, le, ri, v);
        } else if (le > mid) {
            mdf(rc, mid + 1, nri, le, ri, v);
        } else {
            mdf(lc, nle, mid, le, mid, v);
            mdf(rc, mid + 1, nri, mid + 1, ri, v);
        }
        pushUp(p);
    }

    int qry(int p, int nle, int nri, int le, int ri) {
        if (le > ri) {
            return INF;
        }
        if (nle == le && nri == ri) {
            return nd[p];
        }
        pushDown(p);
        int mid = (nle + nri) >> 1, lc = p << 1, rc = lc | 1;
        if (ri <= mid) {
            return qry(lc, nle, mid, le, ri);
        } else if (le > mid) {
            return qry(rc, mid + 1, nri, le, ri);
        } else {
            return min(qry(lc, nle, mid, le, mid),
                       qry(rc, mid + 1, nri, mid + 1, ri));
        }
    }
};

SegTree sgtr;

void moveInto(int u) {
    sgtr.mdf(1, 1, n, dfn[u], post[u], -1);
    sgtr.mdf(1, 1, n, 1, dfn[u] - 1, 1);
    sgtr.mdf(1, 1, n, post[u] + 1, n, 1);
}

void moveOut(int u) {
    sgtr.mdf(1, 1, n, dfn[u], post[u], 1);
    sgtr.mdf(1, 1, n, 1, dfn[u] - 1, -1);
    sgtr.mdf(1, 1, n, post[u] + 1, n, -1);
}

int ans = INF;

void dfs2(int u, int fa) {
    // int temp = min(sgtr.qry(1, 1, n, 1, dfn[u] - 1),
    //                sgtr.qry(1, 1, n, dfn[u] + 1, n)) +
    //            li[u];
    int temp = sgtr.nd[1] + li[u];
    // cerr << "u = " << u << ", fa = " << fa << ", temp = " << temp << endl;
    ans = min(ans, temp);
    for (int v : out[u]) {
        if (v != fa) {
            moveInto(v);
            dfs2(v, u);
            moveOut(v);
        }
    }
    return;
}

int main(void) {
    int T = getInt();
    while (T--) {
        n = getInt();
        for (int i = 1; i <= n; ++i) {
            li[i] = getInt();
        }
        for (int i = 1; i < n; ++i) {
            int u = getInt(), v = getInt();
            out[u].push_back(v);
            out[v].push_back(u);
        }
        tick = 0;
        dfs(1, 0);
        sgtr.init(1, 1, n);
        ans = INF;
        dfs2(1, 0);
        printf("%d\n", ans);

        for (int i = 1; i <= n; ++i) {
            out[i].clear();
        }
    }
    return 0;
}