#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long  LL;
const int N = 100005;
vector <int> factor[N];
vector <int> edge[N];
void init(){
    for(int i=2;i<N;i++){
        factor[i].clear();
        int n = i;
        for(int j=2;j*j<=n;j++){
            if(n%j==0){
                factor[i].push_back(j);
                while(n%j==0) n/=j;
            }
        }
        if(n>1) factor[i].push_back(n);
    }
}
int cnt[N]; ///cnt[i]表示遍历到当前结点时候，含有因数i的结点个数。
int val[N];
int ans[N];
int solve(int n,int val){
    int len = factor[n].size(),ans=0;
    for(int i=1;i<(1<<len);i++){
        int odd = 0;
        int mul = 1;
        for(int j=0;j<len;j++){
            if((i>>j)&1){
                odd++;
                mul*=factor[n][j];
            }
        }
        if(odd&1){
            ans+=cnt[mul];
        }
        else ans-=cnt[mul];
        cnt[mul]+=val; /// val = 1 代表退出当前结点时把因子加上
    }
    return ans;
}
int dfs(int u,int pre){
    int L = solve(val[u],0);  ///第一次遍历到 u,拥有与 u 相同的因子个数
    int s = 0; ///s 代表当前结点下的子节点数目
    for(int i=0;i<edge[u].size();i++){
        int v = edge[u][i];
        if(v==pre) continue;
        s+=dfs(v,u);
    }
    int R = solve(val[u],1);
    ans[u] = s - (R-L);
    if(val[u]==1) ans[u]++;
    return s+1;
}
int main()
{
    init();
    int n,t = 1;
    while(scanf("%d",&n)!=EOF){
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++) edge[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&val[i]);
        }
        dfs(1,-1);
        bool flag = true;
        printf("Case #%d: ",t++);
        for(int i=1;i<=n;i++){
            if(!flag) printf(" ");
            flag = false;
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}