{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"有 $n$ 只可爱的狗子,第 $i$ 只可爱的狗子的可爱值为 $a_i$。可爱的狗子们通过一些姐妹关系形成了一个树状结构。在 $1$ 号狗子是树的根的情况下,$i$ 号狗子的子树内的狗子就是 $i$ 号狗子的妹妹们。\n\n若一只可爱的狗子 $i$ 在玩游戏,那么她会对游戏产生 $f_d(a_i^2)$ 的欢乐值。若两只可爱的狗子 $i,j$ 在一起玩游戏,那么她们会对游戏产生 $f_d(a_ia_j)$ 的欢乐值。一次游戏的欢乐值是所有玩游戏的狗子和狗子对,所贡献的欢乐值的和。\n\n给定常数 $d$。我们将 $z$ 拆解成一些质数的幂次的乘积 $z\u003d\\prod_ip_i^{k_i}$,我们定义:\n$$f_d(z)\u003d\\prod_i(-1)^{k_i}[k_i\\le d]$$\n现在对于每只可爱的狗子 $x$,她打算和她的妹妹们一起玩游戏,希望你能帮她们计算出此次游戏的欢乐值。"}},{"title":"输入格式","value":{"format":"MD","content":"第一行两个整数 $n,d$。\n\n接下来 $n-1$ 行每行描述一条边,第 $i$ 条边为 $u_i,v_i$。保证这 $n-1$ 条边会构成一棵树。\n\n接下来一行 $n$ 个数,第 $i$ 个数代表 $a_i$,保证所有的 $a_i$ 构成一个 $1$ 到 $n$ 的排列。"}},{"title":"输出格式","value":{"format":"MD","content":"输出一共 $n$ 行,每行一个数。第 $i$ 行的数代表编号为 $i$ 的点(狗子)的答案。"}},{"title":"样例 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n1 2\n1 3\n1 2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n$1$ 号狗子的答案:$f_d(1^2)+f_d(2^2)+f_d(3^2)+f_d(1\\times 2)+f_d(1\\times 3)+f_d(2\\times 3)\u003d1+1+1-1-1+1\u003d2$。\n\n$2$ 号狗子的答案:$f_d(2^2)\u003d1$。\n\n$3$ 号狗子的答案:$f_d(3^2)\u003d1$。"}},{"title":"样例 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e20 1\n15 2\n4 15\n9 13\n16 19\n2 5\n13 2\n19 2\n8 14\n1 12\n18 7\n10 5\n3 8\n20 19\n14 2\n7 19\n18 6\n8 11\n17 8\n19 1\n14 3 5 2 9 4 18 16 1 20 13 7 6 12 19 17 10 15 8 11\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2\n0\n0\n0\n0\n0\n0\n1\n0\n0\n0\n2\n0\n1\n0\n0\n0\n3\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"数据范围与提示","value":{"format":"MD","content":"对于 $100\\%$ 的数据满足 $1\\le n\\le 2\\times 10^5,1\\le d\\le 20,1\\le a_i,u_i,v_i\\le n$,保证所有的 $a_i$ 构成一个 $1$ 到 $n$ 的排列。\n\n| 子任务编号 | 子任务分值 | 特殊数据范围 |\n| :--------: | :--------: | :-----------------------------: |\n| subtask 1 | $10$ | $n\\le 500$ |\n| subtask 2 | $10 $ | $n\\le 2000$ |\n| subtask 3 | $10$ | $d\u003d20$ |\n| subtask 4 | $20$ | $d\u003d1,\\forall i,u_i\u003d1,v_i\u003di+1$ |\n| subtask 5 | $15$ | $\\forall i,u_i\u003d1,v_i\u003di+1$ |\n| subtask 6 | $10$ | $n\\le 50000$ |\n| subtask 7 | $25$ | $n\\le 2\\times 10^5$ |"}}]}