← 返回题目列表

AtCoder · pakencamp_2024_day2_b

B. 饼干和蚂蚁

中文机器翻译题面 查看原题

配点 : 100 点

問題文

帕肯公园被称为蚂蚁的栖息地,N 蚂蚁巢和 有 N-1 凹槽。在巢中 1, 2 \ldots N ,在凹槽中 1, 2 \ldots N-1 并按顺序编号。 i (1 \leq i \leq N-1) 是巢 U_i 和巢 V_i 双向连接。在这里,任何 2 两个巢通过多个凹槽在两个方向上连接。

生物学家帕肯先生发现,生活在帕肯公园的蚂蚁有以下习性。 生活在

  • 巣 s (1 \leq s \leq N中的蚂蚁) s 和巢直接通过凹槽连接。 当且仅当有超过 K 块饼干时,从它们的巢中带入饼干。把它带进来后,窝 假设 s 中有一块饼干。请注意,此行为不会导致饼干从原来的巢中消失。

作为一个实验,帕肯先生决定选择几个巢穴,将饼干放入其中,最后调查有多少个巢穴含有饼干。N 来自最初放置饼干的巢。 1 如何选择多个窝 2^N-1 有多种方法可以做到这一点,但对于每种方法,找到饼干存在的最终巢数,并计算巢的总数。 P 求余数。

制約

  • 1 \leq K \leq N \leq 10^6
  • 10^8 \leq P \leq 10^9
  • P 是质数
  • 1 \leq U_i \lt V_i \leq N (1 \leq i \leq N-1)
  • 给定的图是一棵树
  • 所有输入均为整数

小課題

  1. (1 点) K = 1
  2. (1 点) K = N-1
  3. (2 点) N \leq 15
  4. (6 点) U_i = i , V_i = i+1 (1 \leq i \leq N-1)
  5. (35 点) N \leq 2000, K \leq 5
  6. (15 点) K \leq 5
  7. (25 点) N \leq 10^5
  8. (15 点)无附加约束

入力

输入将以以下形式通过标准输入给出。

N K P
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

出力

打印答案。


入力例 1

4 2 998244353
1 2
2 3
3 4

出力例 1

36

例如,先鸟巢 假设您将一块饼干放入 1, 3 中。然后,鸟巢 2 蚂蚁窝 1, 3 的 2 (\geq K) 把饼干从巢穴中拿出来。最后 巢中会有 1,2,3 的 3 饼干。

此示例是一个小作业。 满足 3, 4, 5, 6, 7 约束。


入力例 2

5 2 998244353
1 2
2 3
2 4
1 5

出力例 2

93

此示例是一个小作业。 满足 3, 5, 6, 7 约束。


入力例 3

5 1 998244353
1 2
2 3
2 4
1 5

出力例 3

155

此示例是一个小作业。 满足 1, 3, 5, 6, 7 约束。


入力例 4

5 4 998244353
1 2
1 3
1 4
1 5

出力例 4

81

此示例是一个小作业。 满足 2, 3, 5, 6, 7 约束。


入力例 5

15 2 998244353
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

出力例 5

312049

此示例是一个小作业。 满足 3, 5, 6, 7 约束。