#include<bits/stdc++.h>

using namespace std;
using E=long long;
constexpr __int128 inf=(__int128)1e18+7;

__int128 ksm(E a,E b){
  E ret=1;
  for(int i=0; i<b; i++){
    if((__int128)ret*a>inf) return inf;
    ret=ret*a;
  }
  return ret;
}
int main(){

#ifdef zzafanti
  freopen("in.in","r",stdin);
#endif // zzafanti

  cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);

  int n,d;
  cin>>n>>d;
  vector<int> a(n+1);
  for(int i=1; i<n; i++){
    int x,y;
    cin>>x>>y;
  }
  for(int i=1; i<=n; i++) cin>>a[i];
  vector<int> mu(n+1),primes,st(n+1),w(n+1);
  for(int i=1; i<=n; i++){
    int x=i;
    w[i]=1;
    for(int j=2; j*j<=x; j++){
      if(x%j) continue;
      int s=0;
      while(x%j==0) w[i]*=-1,x/=j,s++;
      if(s>d){
        w[i]=0;
        break;
      }
    }
    if(x>1) w[i]=-w[i];
  }

  mu[1]=1;
  for(int i=2; i<=n; i++){
    if(!st[i]){
      primes.emplace_back(i);
      mu[i]=-1;
    }
    for(auto j:primes){
      if(i*j>n) break;
      st[i*j]=1;
      if(i%j==0){
        mu[i*j]=0;
        break;
      }
      mu[i*j]=mu[i]*mu[j];
    }
  }
  vector<int> rec(n+1);
    vector<vector<int>> divs(n+1);
    vector<E> sum(n+1);
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j+=i){
            divs[j].emplace_back(i);
        }
       // cerr<<i<<' '<<w[i]<<' '<<mu[i]<<endl;
    }
    int ans=0;
    for(E i=1; i<=n; i++){
        E x=0;
        for(auto t:divs[i]) sum[t]+=w[i];
        for(auto t:divs[i]){
            if(ksm(t,d+1)/i>n) continue;
            __int128 tmp=ksm(t,d+1); tmp/=__gcd(tmp,(__int128)i);
            if(tmp>n) continue;
            x+=mu[t]*sum[tmp];
        }
        ans+=w[i]*x;
        rec[i]=w[i]*x;
 //     cout<<i<<' '<<w[i]*x<<endl;
    }

    /*
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        cout<<i*j<<' ';
      }
      cout<<endl;
    }
    cout<<endl;
    for(int i=1; i<=n; i++){
      E x=0;
      for(int j=1; j<=i; j++){
        x+=mu[i*j];
      }
      if(x!=rec[i]){
        cout<<i<<' '<<x<<' '<<rec[i]<<endl;
        assert(0);
      }
      //cout<<i<<' '<<x<<endl;
      /*for(int j=1; j<=n; j++){
        cout<<mu[i*j]<<' ';
      }
      cout<<endl;
    }*/

    cout<<ans<<endl;

    for(int i=1; i<=n; i++){
        E x=0;
        for(auto t:divs[i]){
            __int128 tmp=ksm(t,d+1);
            if((__int128)i*i%tmp==0) x+=mu[t];
        }
        st[i]=x;
    }
    //cout<<T<<endl;

    for(int i=2; i<=n; i++){
      cout<<w[a[i]]*w[a[i]]*st[a[i]]<<'\n';
    }

  return 0;
}