Code

#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Fol(i,k,j) for(int i=(k);i>=(j);i--)

using namespace std;

#define B 1400
#define N 500005
#define K 33005
#define mod 998244353

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

void debug(auto &&...x){
    ((cerr<<x<<' '),...);
    cerr<<'\n';
}

IL int pls(int x,int y){return (x+y>=mod?x+y-mod:x+y);}
IL int sub(int x,int y){return (x-y<0?x-y+mod:x-y);}
IL void Add(int &x,int y){x=pls(x,y);}
IL void Dec(int &x,int y){x=sub(x,y);}
IL int mul(int x,int y){return x*1ll*y%mod;}
IL int qp(int x,int y=mod-2){int ans=1;while(y){if(y&1)ans=mul(ans,x);x=mul(x,x);y>>=1;}return ans;}

int id[N],w[N],c[N],a[N];
basic_string<int> e[N];
int vis[B][16],f[B][K],_f[B][K],coef[B][K],ans[N],cnt,tmp[K];
vi S[N];
int n,k;

void FWT(int *g,int opt){
    for(int len=2,mid=1;len<=(1<<k);len<<=1,mid<<=1){
        for(int j=0;j<(1<<k);j+=len){
            for(int k=j;k<j+mid;k++){
                if(!opt)Add(g[k+mid],g[k]);
                else Dec(g[k+mid],g[k]);
            }
        }
    }
}

int calc(int u,int v){
    int res=0;
    if(id[u] && id[v]){
        For(i,0,(1<<k)-1)tmp[i]=mul(_f[id[u]][i],_f[id[v]][i]);
        FWT(tmp,1);
        For(i,0,(1<<k)-1)Add(res,mul(tmp[i],w[i]));
    }
    if(id[v])for(auto val:S[u])Add(res,mul(coef[id[v]][val],w[val]));
    if(id[u])for(auto val:S[v])Add(res,mul(coef[id[u]][val],w[val]));
    for(auto val:S[u])for(auto val2:S[v])Add(res,w[val|val2]);
    return res;
}

void rebuild(int u,int v){
    if(!id[u])id[u]=++cnt;
    for(auto val:S[u])f[id[u]][val]++;S[u].clear();
    if(id[v])For(i,0,(1<<k)-1)f[id[u]][i]+=f[id[v]][i];
    For(i,0,(1<<k)-1)_f[id[u]][i]=f[id[u]][i],coef[id[u]][i]=f[id[u]][i];
    FWT(_f[id[u]],0);
    for(int len=2,mid=1;len<=(1<<k);len<<=1,mid<<=1){
        int z=__lg(len);
        for(int j=0;j<(1<<k);j+=len){
            for(int k=j;k<j+mid;k++){
                int x=coef[id[u]][k],y=coef[id[u]][k+mid];
                coef[id[u]][k]=pls(x,mul(y,c[z]));
                coef[id[u]][k+mid]=pls(x,y);
            }
        }
    }
    For(i,1,k)vis[id[u]][i]=0;
}

void opr(int u,int t){
    if(vis[id[u]][t])return;vis[id[u]][t]=1;
    For(S,0,(1<<k)-1)if(!(S&(1<<(t-1))))Add(f[id[u]][(S|(1<<(t-1)))],f[id[u]][S]),f[id[u]][S]=0;
    For(i,0,(1<<k)-1)_f[id[u]][i]=f[id[u]][i],coef[id[u]][i]=f[id[u]][i];
    FWT(_f[id[u]],0);
    for(int len=2,mid=1;len<=(1<<k);len<<=1,mid<<=1){
        int z=__lg(len);
        for(int j=0;j<(1<<k);j+=len){
            for(int k=j;k<j+mid;k++){
                int x=coef[id[u]][k],y=coef[id[u]][k+mid];
                coef[id[u]][k]=pls(x,mul(y,c[z]));
                coef[id[u]][k+mid]=pls(x,y);
            }
        }
    }
}


void dfs(int x,int fa){
    S[x].pb((1<<(a[x]-1)));ans[x]=c[a[x]];
    for(auto v:e[x]){
        if(v==fa)continue;
        dfs(v,x);
        //operate
        if(id[v])opr(v,a[x]);
        for(auto &val:S[v])val|=(1<<(a[x]-1));
        //calculate
        Add(ans[x],calc(x,v));Add(ans[x],ans[v]);
        //merge
        for(auto val:S[v])S[x].pb(val);vector<int>().swap(S[v]);
        if(id[v])swap(id[x],id[v]);
        if(id[v] || S[x].size()>B)rebuild(x,v);
    }
}

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif

    n=read(),k=read();
    For(i,1,k)c[i]=read();
    For(i,1,n)a[i]=read();
    For(i,1,n-1){
        int u=read(),v=read();
        e[u]+=v;e[v]+=u;
    }
    For(S,0,(1<<k)-1){
        w[S]=1;
        For(j,1,k)if(S&(1<<(j-1)))w[S]=mul(w[S],c[j]);
    }
    dfs(1,0);
    For(i,1,n)write(ans[i]),putchar(' ');
    return 0;
}