TIOJ 1646

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;}
inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
const ll inf = 1e9, INF = 4e18;
const int N = 200002, L = 18;
int n, r;
int ri[N];
vector<int> adj[N];
vector<int> vir[N];
vector<int> nds[N];

int dep[N], vis[N], tot;
int st[L + 1][N * 2];
void dfs(int u, int p){
    vis[u] = tot++;
    st[0][vis[u]] = u;
    for(int v: adj[u]){
        if(v == p) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        st[0][tot++] = u;
    }
}
void process(){
    tot = 0;
    dfs(1, 0);
    for(int l = 1; l < L + 1; ++l)
        for(int i = 0; i + (1<<l) < tot; ++i)
            st[l][i] = (
                dep[st[l-1][i]] < dep[st[l-1][i + (1<<(l-1))]]
                ? st[l-1][i]
                : st[l-1][i + (1<<(l-1))]
            );
}
int lca(int u, int v){
    u = vis[u], v = vis[v];
    if(u > v) swap(u, v);
    int l = __lg(v - u);
    return (
        dep[st[l][u]] < dep[st[l][v - (1<<l) + 1]]
        ? st[l][u]
        : st[l][v - (1<<l) + 1]
    );
}
int stk[N], top;
void buildVir(vector<int>& nds){
    sort(AI(nds), [](int u, int v){
        return vis[u] < vis[v];
    });
    auto ae = [](int u, int v){
        vir[u].pb(v);
        vir[v].pb(u);
    };
    stk[top = 1] = 1; vir[1].clear();
    for(int i: nds){
        if(i == 1) continue;
        int l = lca(i, stk[top]);
        if(l != stk[top]){
            while(vis[l] < vis[stk[top - 1]])
                ae(stk[top], stk[top - 1]), --top;
            if(vis[l] > vis[stk[top - 1]]){
                vir[l].clear();
                ae(l, stk[top]);
                stk[top] = l;
            } else ae(l, stk[top--]);
        }
        vir[i].clear();
        stk[++top] = i;
    }

    for(int i = 1; i < top; ++i)
        ae(stk[i], stk[i + 1]);
}

int curr;
ll sz[N], dp[N];
void dps(int u, int p){
    sz[u] = (ri[u] == curr), dp[u] = 0;
    for(int v: vir[u]){
        if(v == p) continue;
        dps(v, u);
        dp[u] += sz[v] * sz[v] * (dep[v] - dep[u]);
        dp[u] += dp[v];
        sz[u] += sz[v];
    }
}

void solve(){
    cin >> n >> r;
    for(int i = 1; i <= r; ++i) nds[i].clear();
    for(int i = 1; i <= n; ++i){
        adj[i].clear();
        cin >> ri[i];
        nds[ri[i]].pb(i);
    }
    for(int i = 1, u, v; i < n; ++i){
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    process();
    for(int i = 1; i <= r; ++i){
        buildVir(nds[i]);
        curr = i;
        dps(1, 0);
        cout << i << ": " << dp[1] << '\n';
    }
    cout << '\n';
}

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t; cin >> t;
    for(; t; --t) solve();
    return 0;
}