题目描述
有 n 只可爱的狗子,第 i 只可爱的狗子的可爱值为 ai。可爱的狗子们通过一些姐妹关系形成了一个树状结构。在 1 号狗子是树的根的情况下,i 号狗子的子树内的狗子就是 i 号狗子的妹妹们。
若一只可爱的狗子 i 在玩游戏,那么她会对游戏产生 fd(a2i) 的欢乐值。若两只可爱的狗子 i,j 在一起玩游戏,那么她们会对游戏产生 fd(aiaj) 的欢乐值。一次游戏的欢乐值是所有玩游戏的狗子和狗子对,所贡献的欢乐值的和。
给定常数 d。我们将 z 拆解成一些质数的幂次的乘积 z=∏ipkii,我们定义:
fd(z)=∏i(−1)ki[ki≤d]
现在对于每只可爱的狗子 x,她打算和她的妹妹们一起玩游戏,希望你能帮她们计算出此次游戏的欢乐值。
时空限制
时间限制 1s,空间限制 256MB。
输入格式
第一行两个整数 n,d。
接下来 n−1 行每行描述一条边,第 i 条边为 ui,vi。保证这 n−1 条边会构成一棵树。
接下来一行 n 个数,第 i 个数代表 ai,保证所有的 ai 构成一个 1 到 n 的排列。
输出格式
输出一共 n 行,每行一个数。第 i 行的数代表编号为 i 的点(狗子)的答案。
样例输入1
3 2 1 2 1 3 1 2 3
样例输出1
2 1 1
样例解释
1 号狗子的答案:fd(12)+fd(22)+fd(32)+fd(1×2)+fd(1×3)+fd(2×3)=1+1+1−1−1+1=2。
2 号狗子的答案:fd(22)=1。
3 号狗子的答案:fd(32)=1。
样例输入2
20 1 15 2 4 15 9 13 16 19 2 5 13 2 19 2 8 14 1 12 18 7 10 5 3 8 20 19 14 2 7 19 18 6 8 11 17 8 19 1 14 3 5 2 9 4 18 16 1 20 13 7 6 12 19 17 10 15 8 11
样例输出2
2 2 0 0 0 0 0 0 1 0 0 0 2 0 1 0 0 0 3 0
数据范围
对于 100% 的数据满足 1≤n≤2×105,1≤d≤20,1≤ai,ui,vi≤n,保证所有的 ai 构成一个 1 到 n 的排列。
子任务编号 | 子任务分值 | 特殊数据范围 |
---|---|---|
1 | 10 | n≤500 |
2 | 10 | n≤2000 |
3 | 10 | d=20 |
4 | 20 | d=1,∀i,ui=1,vi=i+1 |
5 | 15 | ∀i,ui=1,vi=i+1 |
6 | 10 | n≤50000 |
7 | 25 | n≤2×105 |