#2019. Lovely Dogs

    ID: 2019 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest755来源:qoj.ac数据:公开样例树形DP深搜

Lovely Dogs

Lovely Dogs

题目描述

标题: Lovely Dogs - Problem - QOJ.ac

#4895. Lovely Dogs

Statistics

题目描述

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

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

给定常数 d。我们将 z 拆解成一些质数的幂次的乘积 z=∏ipiki,我们定义:

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
1 2
1 3
1 2 3
2
1
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
0
0
0
0
0
0
1
0
0
0
2
0
1
0
0
0
3
0