#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 17;
const int inf = 1e9;
const double eps = 1e-11;
string s;
int n, m, k, qq;
void solve() {
    cin >> n;
    vector<int> a(n), logA(n + 1);
    vector<vector<int>> adj(n), deps(n), rmq(n, vector<int>(LOG)), up(n, vector<int>(LOG));
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        rmq[i][0] = a[i];
    }
    
    for (int i = 2; i <= n; i++) {
        logA[i] = logA[i / 2] + 1;
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n - (1 << j) + 1; i++) {
            rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    auto querymn = [&](int l, int r) {
        int sz = r - l + 1;
        int lg = logA[sz];
        return min(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]);
    };
    
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<bool> vis(n);
    vector<int> dep(n), tin(n), tout(n);
    up[0][0] = -1;
    int t = 0;
    auto dfs = [&](int u, auto dfs) -> void {
        vis[u] = true, tin[u] = t++;
        deps[dep[u]].push_back(u);
        for (int v : adj[u]) {
            if (!vis[v]) {
                dep[v] = dep[u] + 1, up[v][0] = u;
                dfs(v, dfs);
            }
        }
        
        tout[u] = t++;
    };
    
    dfs(0, dfs);
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i < n; i++) {
            if (up[i][j - 1] == -1) up[i][j] = -1;
            else up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
    
    auto isancestor = [&](int u, int v) {
        return (tin[u] <= tin[v] && tout[u] >= tout[v]);
    };
    
    auto query = [&](int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        if (isancestor(u, v)) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            int w = up[u][i];
            if (w != -1 && !isancestor(w, v)) u = w;
        }
        
        return up[u][0];
    };
    
    vector<vector<int>> viradj(n);
    vector<int> dp(n);
    ll out = a[0];
    // dbg(deps);
    // dbg(tin);
    // dbg(tout);
    // dbg(rmq);
    // dbg(up);
    for (int i = 1; i < n; i++) {
        int sz = deps[i].size();
        if (sz == 0) break;
        vector<pi> nodes(sz);
        for (int j = 0; j < sz; j++) {
            nodes[j] = {tin[deps[i][j]], deps[i][j]};
        }
        
        sort(nodes.begin(), nodes.end());
        stack<int> stk;
        stk.push(0);
        vector<pi> used;
        used.push_back({0, 0});
        // dbg(nodes);
        for (int j = 0; j < sz; j++) {
            auto [temp, u] = nodes[j];
            used.push_back({dep[u], u});
            while (stk.size() > 1) {
                int v = stk.top();
                int lca = query(u, v);
                if (isancestor(v, u)) break;
                stk.pop();
                int vv = stk.top();
                if (dep[vv] <= dep[lca]) {
                    if (vv != lca) stk.push(lca);
                    viradj[lca].push_back(v);
                    used.push_back({dep[lca], lca});
                    break;
                }
                
                viradj[vv].push_back(v);
            }
            
            stk.push(u);
        }
        
        // dbg(viradj);
        // dbg(stk.size());
        while (stk.size() > 1) {
            int v = stk.top();
            stk.pop();
            int vv = stk.top();
            viradj[vv].push_back(v);
        }
        
        sort(used.rbegin(), used.rend());
        for (auto [d, u] : used) {
            int sum = 0, cnt = 0;
            for (int v : viradj[u]) {
                sum += dp[v], cnt++;
            }
            
            dp[u] = min((cnt == 0 ? inf : sum), querymn(i - d, i));
        }
        
        // dbg(dp);
        // dbg(viradj);
        // dbg(dp[0]);
        out += dp[0];
        for (auto [d, u] : used) {
            viradj[u].clear();
            dp[u] = 0;
        }
    }
    
    cout << out << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}