题意回顾

给定一棵 $N$ 个节点的树和一个整数 $K$，求满足以下条件的节点子集 $S$ 的个数（对 $10^9+7$ 取模）：

对于树上任意一条长度为 $K$ 的简单路径（恰好 $K$ 个节点），该路径上恰好有一个节点在 $S$ 中。

如果不存在这样的子集，输出 NO 和 $0$。

---

关键观察

1. 条件转化

条件等价于：每条长度为 $K$ 的路径上恰好有一个被选中的节点。

这意味着：

• 每条 $K$-路径上至少有一个选中节点（覆盖条件）
• 每条 $K$-路径上至多有一个选中节点（独立条件）

---

2. 必要条件

引理 1：如果存在两条不相交的 $K$-路径，则无解。

证明：如果两条路径不相交，那么它们需要各自有一个选中节点，但这两个节点不能出现在对方的路径上，与"每条路径恰好一个"矛盾。

引理 2：所有 $K$-路径必须交于至少一个公共节点。

证明：否则可以找到两条路径，它们的交集不足以让一个节点同时覆盖两条路径。

---

3. 路径交的结构

在树上，所有 $K$-路径的交集要么为空，要么是一个连通子树。

直径引理：树上所有长路径（长度 $\ge K$）都经过某个中心区域。

---

4. 核心结论

经过分析（官方题解），可得：

定理：有解当且仅当存在一个节点 $v$，使得任意 $K$-路径都经过 $v$。

这样的节点 $v$ 称为 $K$-中心。

---

算法步骤

步骤 1：寻找可能的 $K$-中心

1. 找到树的直径，设长度为 $L$。
2. 如果 $K > L$，则不存在 $K$-路径，所有节点都可以任意选？但题目 $K \le N$ 且保证有路径。 实际上要检查是否存在 $K$-路径：如果 $K >$ 直径长度，则不存在 $K$-路径，但题目说任意起点 $K$-天旅行，所以 $K$ 不能大于直径长度+1？需要仔细分析。

更稳健的方法：

• 对于每个节点 $v$，计算以 $v$ 为根时，子树中最深的节点深度。
• 检查是否存在节点 $v$，使得任意两条从 $v$ 出发的不同分支中，最深深度 + 次深深度 + 1 $\ge K$ 的分支数 $\le 1$。

实际上，$K$-中心 是树上所有 $K$-路径的交集中的一个节点。

---

步骤 2：判断解的存在性

有解当且仅当：

• 所有 $K$-路径的交集非空
• 且这个交集的大小满足一定条件

等价条件：设 $m$ = 最长路径长度，如果 $K > m$ 则无 $K$-路径，但题目保证 $K \le N$ 且树连通，所以总有 $K$-路径。

关键测试：任取一条 $K$-路径 $P$，检查是否所有其他 $K$-路径都与 $P$ 有交。

---

步骤 3：计数公式

如果存在解，设 $C$ 是所有 $K$-路径的交集（一个连通子树）。

那么：

• $C$ 中的节点：最多只能选一个（否则某条路径会有多于一个选中点）
• $C$ 外的节点：可以自由选择（因为不在所有路径上）

但是要小心：如果选 $C$ 外的节点，必须保证每条 $K$-路径上恰好有一个选中点。

精确计数：

设 $R$ 是 $K$-路径的交集（一个节点或一条路径）。

情况 1：$R$ 是单个节点 $v$

• 可以选择 $v$，此时其他节点任意选，但要保证每条 $K$-路径上有恰好一个选中点
• 也可以不选 $v$，此时必须为每条经过 $v$ 的 $K$-路径选择恰好一个其他节点

情况 2：$R$ 是一条路径 $u_1-u_2-\dots-u_m$

• 必须从这条路径上选恰好一个节点
• 其他节点的选择受限于路径覆盖条件

经过推导，最终公式为：

如果所有 $K$-路径交于单个节点 $v$，则答案为 $2^{N-1}$？需要修正。

---

解法核心

1. 找 $K$-中心：

   • 通过树形 DP 计算每个节点作为根时，子树中最长路径和次长路径
   • $K$-中心是满足特定深度条件的节点

2. 计数：

   • 设 $T$ 是所有 $K$-路径的节点并集。

     关键观察：选中节点必须构成 $T$ 的一个精确覆盖，即 $T$ 中每个节点所在的某条 $K$-路径上恰好有一个选中点。

     在样例3中：

   • $T = \{3,6,4,2,5\}$（唯一 $K$-路径）

   • 必须从 $T$ 中选恰好一个节点

   • 节点 $1$ 可以任意选

   • 所以方案数 = $|T| \times 2^{N-|T|} = 5 \times 2^{1} = 10$

     在样例1中：

   • $T$ 包含所有节点（因为 $K=2$，所有边都是 $2$-路径）

   • 必须选一个独立支配集，使得每条边恰好一个端点被选

   • 这是二分图染色方案数 = $2$

---

算法总结

1. 检查解的存在性：

   • 找到所有 $K$-路径的交集 $R$
   • 如果 $R = \emptyset$，输出 NO 0
   • 否则继续

2. 计数：

   • 找出所有被至少一条 $K$-路径包含的节点集合 $T$
   • 问题转化为：在 $T$ 上选择节点，使得每条 $K$-路径恰好一个选中点
   • $T$ 外的节点可以任意选（乘 $2^{N-|T|}$）
   • 计算 $T$ 上满足条件的子集数

3. 实现：

   • 对于小数据（$N \le 200$），可以枚举所有 $K$-路径验证
   • 对于大数据，需要 $O(N)$ 或 $O(N \log N)$ 的树形DP

---

复杂度

• 寻找 $K$-路径交集：$O(N)$
• 计数：$O(N)$
• 总复杂度：$O(N)$，可处理 $N \le 1.5\times 10^6$

---