QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 4895. Lovely Dogs

Statistics

题目描述

有 $n$ 只可爱的狗子,第 $i$ 只可爱的狗子的可爱值为 $a_i$。可爱的狗子们通过一些姐妹关系形成了一个树状结构。在 $1$ 号狗子是树的根的情况下,$i$ 号狗子的子树内的狗子就是 $i$ 号狗子的妹妹们。

若一只可爱的狗子 $i$ 在玩游戏,那么她会对游戏产生 $f_d(a_i^2)$ 的欢乐值。若两只可爱的狗子 $i,j$ 在一起玩游戏,那么她们会对游戏产生 $f_d(a_ia_j)$ 的欢乐值。一次游戏的欢乐值是所有玩游戏的狗子和狗子对,所贡献的欢乐值的和。

给定常数 $d$。我们将 $z$ 拆解成一些质数的幂次的乘积 $z=\prod_ip_i^{k_i}$,我们定义:

$$ f_d(z)=\prod_i(-1)^{k_i}[k_i\le d] $$

现在对于每只可爱的狗子 $x$,她打算和她的妹妹们一起玩游戏,希望你能帮她们计算出此次游戏的欢乐值。

时空限制

时间限制 1s,空间限制 256MB。

输入格式

第一行两个整数 $n,d$。

接下来 $n-1$ 行每行描述一条边,第 $i$ 条边为 $u_i,v_i$。保证这 $n-1$ 条边会构成一棵树。

接下来一行 $n$ 个数,第 $i$ 个数代表 $a_i$,保证所有的 $a_i$ 构成一个 $1$ 到 $n$ 的排列。

输出格式

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

样例输入1

3 2
1 2
1 3
1 2 3

样例输出1

2
1
1

样例解释

$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)=1+1+1-1-1+1=2$。

$2$ 号狗子的答案:$f_d(2^2)=1$。

$3$ 号狗子的答案:$f_d(3^2)=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\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$ 的排列。

子任务编号 子任务分值 特殊数据范围
1 10 $n\le 500$
2 10 $n\le 2000$
3 10 $d=20$
4 20 $d=1,\forall i,u_i=1,v_i=i+1$
5 15 $\forall i,u_i=1,v_i=i+1$
6 10 $n\le 50000$
7 25 $n\le 2\times 10^5$