#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;

inline int read() {
	char ch = getchar(); int x = 0;
	while (!isdigit(ch)) {ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
	return x;
}

struct node {
	int p, c;
	node(int a = 0, int b = 0) {p = a; c = b;}
};
int n, D, prime[N], cnt, val[N], lim[N], a[N], id[N], pw[N][21], u[N], depth[N], fa[N][18];
vector<node> vec[N];
vector<int> g[N];
bitset<N> vis;

void init() {
	u[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) {
			prime[++cnt] = i; u[i] = -1;
			pw[i][0] = 1;
			for (int j = 1; j <= D; ++j) pw[i][j] = min(1ll * pw[i][j - 1] * i, 1000000000ll);
		}
		for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {
			vis[i * prime[j]] = 1;
			if (i % prime[j]) u[i * prime[j]] = -u[i];
			else {
				u[i * prime[j]] = 0;
				break;
			}
		}
	}
	for (int i = 2, x, o; i <= n; ++i) {
		x = i;
		for (int j = 1; j <= cnt && prime[j] * prime[j] <= x; ++j) {
			if (x % prime[j]) continue;
			o = 0;
			while (x % prime[j] == 0) x /= prime[j], o++;
			vec[i].push_back(node(prime[j], o));
			val[i] += o; lim[i] = max(lim[i], o);
		}
		if (x > 1) vec[i].push_back(node(x, 1)), val[i]++, lim[i] = max(lim[i], 1);
		val[i] &= 1;
	}
}
	
void dfs(int x, int pa, int d) {
	fa[x][0] = pa; depth[x] = d;
	for (auto y : g[x]) {
		if (y == pa) continue;
		dfs(y, x, d + 1);
	}
}

inline int LCA(int x, int y) {
	if (depth[x] < depth[y]) swap(x, y);
	int tmp = depth[x] - depth[y];
	for (int i = 0; i <= 17; ++i)
		if ((tmp >> i) & 1) x = fa[x][i];
	if (x == y) return x;
	for (int i = 17; i >= 0; --i) {
		if (fa[x][i] == fa[y][i]) continue;
		x = fa[x][i]; y = fa[y][i];
	}
	return fa[x][0];
}

namespace subtask1 {
	const int N1 = 2005;
	int ans[N1];
	
	void dfs1(int x) {
		for (auto y : g[x]) {
			if (y == fa[x][0]) continue;
			dfs1(y); ans[x] += ans[y];
		}
	}
	
	void solve() {
		for (int p = 1; p <= n; ++p)
			for (int q = p; q <= n; ++q) {
				int lca = LCA(p, q), x = a[p], y = a[q];
				int i = 0, mx = max(lim[x], lim[y]);
				for (auto tmp : vec[x]) {
					while (i < vec[y].size() && vec[y][i].p < tmp.p) i++;
					if (i < vec[y].size() && vec[y][i].p == tmp.p) mx = max(mx, vec[y][i].c + tmp.c);
				}
				if (mx > D) continue;
				if (val[x] ^ val[y]) ans[lca]--;
				else ans[lca]++;
			}
		dfs1(1);
		for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
	}
}

namespace subtask2 {
	int sz[N][2];
	ll dp[N], ex[N];
	map<int, bool> mp;
	
	void dfs1(int x) {
		dp[x] = sz[x][val[a[x]]] = (lim[a[x]] <= D);
		for (auto y : g[x]) {
			if (y == fa[x][0]) continue;
			dfs1(y);
			dp[x] += dp[y];
			dp[x] += 1ll * sz[x][0] * sz[y][0];
			dp[x] += 1ll * sz[x][1] * sz[y][1];
			dp[x] -= 1ll * sz[x][0] * sz[y][1];
			dp[x] -= 1ll * sz[x][1] * sz[y][0];
			sz[x][0] += sz[y][0];
			sz[x][1] += sz[y][1];
		}
	}
	
	void dfs2(int x) {
		for (auto y : g[x]) {
			if (y == fa[x][0]) continue;
			dfs2(y); ex[x] += ex[y];
		}
	}
	
	void solve() {
		dfs1(1);
		for (int i = 1; i <= n; ++i) {
			if (lim[i] > D) continue;
			mp.clear();
			for (auto tmp : vec[i]) {
				int mn = pw[tmp.p][D + 1 - tmp.c];
				if (mn > n) continue;
				int now = mn;
				if (now < i) now = ((i - 1) / now + 1) * now;
				if (now > n) continue;
				while (now <= n) {
					if (lim[now] > D) {now += mn; continue;}
					if (mp[now]) {now += mn; continue;}
					mp[now] = true;
					int x = id[i], y = id[now], lca = LCA(x, y);
					if (val[i] ^ val[now]) ex[lca]--;
					else ex[lca]++;
					now += mn;
				}
			}
		}
		dfs2(1);
		for (int i = 1; i <= n; ++i) printf("%lld\n", dp[i] - ex[i]);
	}
}

namespace subtask3 {
	int sz[N][2]; ll ans;
	
	void solve() {
		for (int i = 1; i <= n; ++i)
			for (int j = 1; 1ll * i * j <= n; ++j) {
				if (u[i * j] == 0) continue;
				sz[i][val[i * j]]++;
			}
		for (int i = 1; i <= n; ++i) {
			ans += 1ll * u[i] * sz[i][0] * sz[i][0];
			ans += 1ll * u[i] * sz[i][1] * sz[i][1];
			ans -= 1ll * u[i] * sz[i][0] * sz[i][1];
			ans -= 1ll * u[i] * sz[i][1] * sz[i][0];
		}
		ans = (ans + 1) / 2; printf("%lld\n", ans);
		for (int i = 2; i <= n; ++i) printf("%d\n", a[i] == 1);
	}
}

int main() {
//	freopen("in.in", "r", stdin);
//	freopen("mine.out", "w", stdout);
	n = read(); D = read(); init();
	for (int i = 1, x, y; i < n; ++i) {
		x = read(); y = read();
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i) a[i] = read(), id[a[i]] = i;
	dfs(1, 0, 1);
	for (int j = 1; j <= 17; ++j)
		for (int i = 1; i <= n; ++i)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	
	return subtask3 :: solve(), 0;
	
	if (n <= 2000) subtask1 :: solve();
	else if (D == 20) subtask2 :: solve();
	else if (g[1].size() == n - 1 && D == 1) subtask3 :: solve();
	return 0;
}