T209792 Lovely Dogs

有 $n$ 只可爱的狗子，第 $i$ 只可爱的狗子的可爱值为 $a_i$。可爱的狗子们通过一些姐妹关系形成了一个树状结构。在 $1$ 号狗子是树的根的情况下，$i$ 号狗子的子树内的狗子就是 $i$ 号狗子的妹妹们。 若一只可爱的狗子 i 在玩游戏，那么她会对游戏产生 $f_d(a_i^2)$ 的欢乐值。若两只可爱的狗子 $i,j$ 在一起玩游戏，那么她们会对游戏产生 $f_d(a_ia_j)$ 的欢乐值。一次游戏的欢乐值是所有玩游戏的狗子和狗子对，所贡献的欢乐值的和。 给定常数 $d$。我们将 $z$ 拆解成一些质数的幂次的乘积 $z=∏_ip_i^{k_i}$，我们定义： $f_d(z)=∏_i(−1)^{k_i}[k_i≤d]$ 现在对于每只可爱的狗子 $x$，她打算和她的妹妹们一起玩游戏，希望你能帮她们计算出此次游戏的欢乐值。

第一行两个整数 $n,d$。 接下来 $n−1$ 行每行描述一条边，第 $i$ 条边为 $u_i,v_i$。保证这 $n−1$ 条边会构成一棵树。 接下来一行 $n$ 个数，第 $i$ 个数代表 $a_i$，保证所有的 $a_i$ 构成一个 $1$ 到 $n$ 的排列。

输出一共 $n$ 行，每行一个数。第 $i$ 行的数代表编号为 $i$ 的点（狗子）的答案。

$1$ 号狗子的答案：$f_d(1^2)+f_d(2^2)+f_d(3^2)+f_d(1×2)+f_d(1×3)+f_d(2×3)=1+1+1−1−1+1=2$ $2$ 号狗子的答案：$f_d(2^2)=1$。 $3$ 号狗子的答案：$f_d(3^2)=1$。 #### 数据范围 对于 100% 的数据满足 $1≤n≤2×10^5,1≤d≤20,1≤a_i,u_i,v_i≤n,$ 保证所有的 $a_i$ 构成一个 $1$ 到 $n$ 的排列。 ##### 子任务编号 子任务分值 特殊数据范围 subtask 1 $\space\space\space\space10$ $\space\space\space\space\space\space n≤500$ subtask 2 $\space\space\space\space10$ $\space\space\space\space\space\space n≤2000$ subtask 3 $\space\space\space\space10$ $\space\space\space\space\space\space d=20$ subtask 4 $\space\space\space\space20$ $\space\space\space\space\space\space d=1,∀i,u_i=1,v_i=i+1$ subtask 5 $\space\space\space\space15$ $\space\space\space\space\space\space∀i,u_i=1,v_i=i+1$ subtask 6 $\space\space\space\space10$ $\space\space\space\space\space\space n≤50000$ subtask 7 $\space\space\space\space25$ $\space\space\space\space\space\space n≤2×10^5$ #### 来源：MJJtest 20211107 T1