题解：树上状态等价类与组合计数分析

---

问题分析

本题要求在树上放置 $K$ 头奶牛（每节点至多一头），奶牛可以在树上移动到相邻的空节点。两个初始状态如果可以通过一系列移动互相转换，则称为等价的。我们需要计算每个 $K$ 的不等价状态类数。

等价状态类数实际上就是在考虑对称性（可移动性）后，不同的奶牛放置方案数。

---

关键观察

1. 移动的实质

奶牛在树上的移动类似于「推箱子」游戏，但更简单：只要目标节点为空，奶牛就可以移动过去。这导致：

• 奶牛之间可以交换位置
• 奶牛可以"绕圈"移动
• 但某些位置关系是固定的，无法通过移动改变

2. 度数与可移动性

考虑一个节点的度数（相邻边数）。如果节点度数很小，那么通过该节点的路径受限，可能限制奶牛的排列。

3. 从 $K=N$ 倒推

当 $K=N$ 时，所有节点都被占据，没有移动空间，等价类数就是 $N!$（所有排列）。

随着 $K$ 减少，空位增多，移动可能性增加，等价类数减少。

---

算法框架

第一步：度数分析

对于每个节点 $v$，设其度数为 $deg(v)$。考虑以 $v$ 为根的子树。

第二步：子树贡献计算

对于每个节点 $v$，计算它的子树对答案的贡献：

• 设 $v$ 有 $c$ 个子节点（在某个根下）
• 这些子节点对应的子树大小分别为 $s_1, s_2, \dots, s_c$
• 当 $K$ 较大时，这些子树内部的奶牛排列受限

第三步：动态规划计算

使用树形 DP 计算每个 $K$ 的答案。设 $f[v][j]$ 表示以 $v$ 为根的子树中放置 $j$ 头奶牛的等价类数。

转移时考虑 $v$ 的每个子节点 $u$：

$$f[v][j] = \sum_{k=0}^{min(j, size[u])} \binom{j}{k} \cdot f[u][k] \cdot f[v][j-k] $$

其中 $\binom{j}{k}$ 表示从 $j$ 个位置中选择 $k$ 个给子节点 $u$ 的子树。

第四步：度数约束处理

关键点：当 $K > N - \text{某个值}$ 时，某些排列是不可能的。具体来说：

• 对于度数为 $d$ 的节点，如果 $K > N - (d-1)$，那么通过该节点的路径受限
• 实际上，等价类数等于 $\frac{N!}{\prod_{v} (deg(v)-1)!}$ 当 $K$ 足够大时

第五步：公式推导

最终发现答案有简洁公式： 设 $D = \sum_{v} (deg(v) - 1)$，则对于 $K \ge N-D$，有

$$\text{ans}(K) = \frac{N!}{(N-K)! \cdot \prod_{v} (deg(v)-1)!} $$

对于 $K < N-D$，情况更复杂，但可以通过 DP 计算。

---

实现优化

1. 组合数预处理：预处理阶乘和逆元，用于计算组合数
2. FFT/NTT 优化：DP 转移是卷积形式，可以用 FFT/NTT 加速到 $O(N \log^2 N)$
3. 子树大小限制：DP 时只枚举到子树大小，优化复杂度

---

复杂度分析

• 时间复杂度：
  • 朴素 DP：$O(N^2)$，对于 $N \le 100$ 可行
  • 优化后：$O(N \log^2 N)$ 或 $O(N \sqrt{N})$，对于 $N \le 10^5$ 可行
• 空间复杂度：$O(N)$

---

总结

本题是一道树上的组合计数与等价类分析难题，主要考察：

1. 组合直觉：理解奶牛移动的本质，将问题转化为排列计数
2. 度数分析：发现节点度数对等价类数的关键影响
3. 动态规划：使用树形 DP 计算不同 $K$ 的答案
4. 公式推导：从具体分析中提炼出简洁的数学公式

算法的核心在于：

• 认识到当空位较少时，等价类数由节点的度数决定
• 通过巧妙的组合计数，将问题分解为子树贡献的乘积
• 使用 DP 处理一般情况，公式处理特殊情况

这种"从极端情况（$K=N$）出发，逐步分析空位影响"的方法是解决此类动态等价类问题的有效思路。本题将树的结构特性与组合数学完美结合，是一道质量很高的题目。