#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define pb push_back #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return x*f;} const int MAXN=500010,N=5e5; int n,a[MAXN],f[MAXN],g[MAXN]; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} struct treearray{ int C[MAXN]; int lb(int x){return x&(-x);} void upd(int x,int y){for(int i=x;i<=N;i+=lb(i))C[i]+=y;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i];return res;} int qry(int l,int r){return qry(r)-qry(l-1);} }A,B; void dfs(int u,int lst){ f[u]=A.qry(a[u]+1,N),g[u]=-B.qry(a[u]+1,N); A.upd(a[u],1); for(inx(u))if(v!=lst)dfs(v,u); g[u]+=B.qry(a[u]+1,N); B.upd(a[u],1),A.upd(a[u],-1); } int as[MAXN]; void slv(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(),h[i]=0;CNT=1; for(int i=1;i<n;i++){ int u=read(),v=read(); add_side(u,v); } dfs(1,1); a[0]=0; for(int i=1;i<=n;i++)a[i]=g[i]-f[i],a[0]+=f[i]; sort(a+1,a+n+1); for(int i=1;i<=n;i++)a[i]+=a[i-1]; for(int i=0;i<=n;i++)printf("%lld ",(n-i)*(n-i-1)/2+a[i]);puts(""); } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); int _=read();while(_--) slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }