AT_pakencamp_2024_day2_b Biscuit and Ants

以蚂蚁的栖息地著称的 Paken 公园有 $N$ 个蚁巢和 $N-1$ 条沟渠。蚁巢编号为 $1, 2, \ldots, N$，沟渠编号为 $1, 2, \ldots, N-1$。第 $i$ 条沟渠（$1 \leq i \leq N-1$）连接巢 $U_i$ 与巢 $V_i$，且是双向的。在这里，任意两个巢都可以通过某些沟渠相互连通。 生物学家 Paken 发现了 Paken 公园蚂蚁特有的行为习性： - 住在巢 $s$（$1 \leq s \leq N$）的蚂蚁只有在与巢 $s$ 直接通过沟渠相连的不少于 $K$ 个巢中存在饼干时，才会从这些巢把饼干搬到巢 $s$。一旦搬入，巢 $s$ 就会被视为有饼干。需要注意的是，这一行为不会让原有巢中的饼干减少。 作为实验，Paken 选择若干个蚁巢，最初在这些巢中投放饼干，并调查最终有饼干的蚁巢数。对于所有从 $N$ 个巢中选择至少一个巢最初投放饼干的方法（共 $2^N-1$ 种），对于每种情况，请计算最终有饼干的蚁巢数，并将所有情况的总和对 $P$ 取模输出。

输入通过标准输入给出，格式如下： > $N$ $K$ $P$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_{N-1}$ $V_{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$ 分）无附加限制 ## 样例解释 1 例如，最初在巢 $1, 3$ 投放饼干，则巢 $2$ 的蚂蚁会从巢 $1, 3$（$2 \geq K$）搬来饼干。最终 $1,2,3$ 这 $3$ 个巢中有饼干。 本样例符合小题目 $3,4,5,6,7$ 的限制。 ## 样例解释 2 本样例符合小题目 $3,5,6,7$ 的限制。 ## 样例解释 3 本样例符合小题目 $1,3,5,6,7$ 的限制。 ## 样例解释 4 本样例符合小题目 $2,3,5,6,7$ 的限制。 ## 样例解释 5 本样例符合小题目 $3,5,6,7$ 的限制。 ## 约束条件 - $1 \leq K \leq N \leq 10^6$ - $10^8 \leq P \leq 10^9$ - $P$ 是质数 - $1 \leq U_i < V_i \leq N$（$1 \leq i \leq N-1$） - 给出的图是一棵树 - 所有输入均为整数 由 ChatGPT 5 翻译