#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i--)
#define py puts("Yes")
#define pn puts("No")
#define pt puts("")
#define pb push_back
#define wt(x) write(x),puts("")
#define wr(x) write(x) ,putchar(' ')
#define tx printf("fds")
#define mp make_pair
#define fi first
#define se second
inline int read(){
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*k;
}
void write(int x){
	if(x<0){
		x=-x;
		putchar('-');
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int power(int x,int y,int mod){
	int num=1;
	while(y){
		if(y&1) num=(num*x)%mod;
		x=x*x%mod;
		y>>=1;
	}
	return num;
}
int mul(int x,int y,int mod){
	int num=0;
	while(y){
		if(y&1) num=(num+x)%mod;
		x=(x+x)%mod;
		y>>=1;
	}
	return num;
}
const int N=1e6+7,mod=998244353;
int n,m,tot,cnt,ans,k;
int a[N],b[N];
int head[N];
struct edge{
    int to,next;
}e[N];
void add(int u,int v){
    e[++tot]={v,head[u]};
    head[u]=tot;
}
struct tree{
    int ls,rs;
    int num;
}t[N];
int siz[N],dep[N],son[N],mdep[N],top[N];
int rt[N];
int rmq[N][20];
int newnode(int x){
    t[x]={0,0,0};
    return x;
}
void pu(int id){
    int x=0,y=0;
    if(t[id].ls) x=t[t[id].ls].num;
    if(t[id].rs) y=t[t[id].rs].num;
    t[id].num=x+y;
}
void update(int id,int l,int r,int x,int k){
    if(l==r){
        t[id].num=k;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        if(!t[id].ls) t[id].ls=newnode(++cnt);
        update(t[id].ls,l,mid,x,k);
    }
    else{
        if(!t[id].rs) t[id].rs=newnode(++cnt);
        update(t[id].rs,mid+1,r,x,k);
    }
    pu(id);
}
int RMQ(int l,int r){
    int x=log2(r-l+1);
    return min(rmq[l][x],rmq[r-(1<<x)][x]);
}
int merge(int dp,int x,int y,int l,int r){
    if(!x||!y) return x+y;
    if(l==r){
        t[x].num=min(t[x].num+t[y].num,RMQ(l-dp+1,l+1));
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=merge(dp,t[x].ls,t[y].ls,l,mid);
    t[x].rs=merge(dp,t[x].rs,t[y].rs,mid+1,r);
    pu(x);
    return x;
}
void dfs(int u,int fa){
    dep[u]=mdep[u]=dep[fa]+1;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        mdep[u]=max(mdep[u],mdep[v]);
        if(mdep[v]>mdep[son[u]]){
            son[u]=v;
        }
    }
}
void dfs1(int u,int fa,int tp){
    top[u]=tp;
    if(u==tp) rt[u]=newnode(++cnt);
    update(rt[top[u]],1,n,dep[u],b[dep[u]-dep[top[u]]]);
    if(son[u]) dfs1(son[u],u,tp);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa||v==son[u]) continue;
        dfs1(v,u,v);
    }
}
void dfs2(int u,int fa){
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa) continue;
        dfs2(v,u);
        if(son[u]!=v) rt[top[u]]=merge(dep[u],rt[top[u]],rt[v],1,n);
    }
}
signed main(){
	int tt=read();
	while(tt--){
		tot=0;
        n=read();
        fo(i,1,n) head[i]=0,rt[i]=0,son[i]=0,siz[i]=0,dep[i]=0,mdep[i]=0,top[i]=0;
        fo(i,0,n-1) a[i]=read(),b[i]=a[i];
        fo(i,1,n-1)b[i]=min(b[i],b[i-1]);
        fo(i,1,n){
            rmq[i][0]=a[i-1];
        }
        fo(i,1,19){
            fo(j,1,n){
                rmq[j][i]=min(rmq[j][i-1],rmq[j+(1<<(i-1))][i-1]);
            }
        }
        fo(i,2,n){
            int x=read(),y=read();
            add(x,y);
            add(y,x);
        }
        cnt=0;
        dfs(1,0);
        dfs1(1,0,1);
        dfs2(1,0);
        wt(t[rt[1]].num);
	}
	return 0;
}