题解

问题分析

我们需要找出所有可能的有根树 $D$，使得：

• $D$ 的每个节点的子树复制（涂红）可以挂到初始树（$M$ 个绿色节点）上
• 最终得到给定的树 $T$
• 两个 $D$ 结构不同则视为不同的方案

关键观察

1. 绿色节点的性质：

   • 初始的 $M$ 个绿色节点构成 $T$ 的一个连通子树
   • 这个连通子树包含根节点 $1$
   • 绿色节点之间原本就有边连接

2. 红色节点的性质：

   • 每个红色连通分支对应 $D$ 中某个节点的子树
   • 同一个 $D$ 的不同节点的装饰子树可能在 $T$ 中出现多次
   • 红色节点只能通过一条边连接到绿色节点

3. 结构约束：

   • $T$ 中所有同构的红色子树可能对应 $D$ 中同一个节点的子树
   • $D$ 本身也是一个有根树，需要满足自洽性

算法思路

1. 树哈希与同构分类

首先为 $T$ 的每个节点计算子树哈希值，用于识别同构的子树：

def tree_hash(u, parent):
    values = []
    for v in children[u]:
        if v != parent:
            tree_hash(v, u)
            values.append(hash[v])
    # 排序以确保同构识别
    values.sort()
    hash[u] = compute_hash(values)

2. 寻找可能的绿色连通子树

我们需要找到所有大小为 $M$ 且包含根节点 $1$ 的连通子树。使用树形DP：

设 $dp[u][k]$ 表示以 $u$ 为根的子树中，选择包含 $u$ 的大小为 $k$ 的连通子树的方案数。

转移：

$$dp[u][k] = \sum_{\substack{\sum k_i = k-1 \\ k_i \leq |\text{subtree}(v_i)|}} \prod_{v \in \text{children}(u)} dp[v][k_i] $$

3. 验证候选绿色集合

对于每个候选的绿色节点集合 $S$（大小为 $M$ 且连通）：

• 红色部分 = $T \setminus S$
• 红色部分由若干子树组成，每个都挂到 $S$ 中的某个节点上

我们需要检查是否存在一个树 $D$，使得：

• $D$ 的每个节点的子树同构于红色部分中的某个连通分支
• $D$ 中节点 $i$ 的子树大小等于对应的红色连通分支的大小
• $D$ 的结构与附着关系一致

4. $D$ 的计数

对于固定的绿色集合 $S$，红色部分给出了 $D$ 的"子树频谱"。

设红色部分有 $k$ 个不同的同构类，第 $i$ 类出现了 $c_i$ 次。

那么 $D$ 必须满足：

• $D$ 的节点数等于不同的红色连通分支数
• $D$ 的子树大小分布与红色部分的分布匹配

这转化为：计算有多少个有根树 $D$，其每个节点的子树大小分布与观察到的匹配。

使用生成函数和树计数： 设 $F(x)$ 是 $D$ 的生成函数，满足：

$$F(x) = x \cdot \prod_{i} (1 + F(x) + F(x)^2 + \cdots + F(x)^{c_i}) $$

优化实现

对于小数据（$N \leq 200$）

可以枚举所有可能的绿色连通子树，对每个候选验证并计数。

对于大数据（$N \leq 500000$）

需要更高效的方法：

1. 绿色节点识别：

   • 绿色节点在 $T$ 中形成连通子图
   • 从根开始，绿色节点倾向于集中在顶部
   • 可能只有 $O(\log N)$ 种不同的绿色集合候选

2. 批量处理同构类：

   • 使用哈希快速识别同构子树
   • 对每个同构类批量处理

3. 动态规划优化：

   • 使用生成函数和 FFT 加速卷积
   • 利用树链剖分优化

样例分析

样例1

N=8, M=3
T: 根1，孩子2,3,4; 2有孩子5,6; 3有孩子7,8

唯一的绿色集合：{1,2,3}（或{1,2,4}，但对称） 红色部分：{4,5,6,7,8} 形成特定的结构 对应的 $D$ 只有一种可能。

样例2

N=14, M=5

有两种不同的绿色集合选择，对应两种不同的 $D$ 结构。

复杂度分析

• 树哈希：$O(N)$
• 寻找绿色候选：$O(N \cdot M)$（使用树形DP）
• 验证和计数：$O(\text{同构类数} \cdot \text{多项式乘法})$
• 总体：对于小数据可行，大数据需要优化

实现细节

1. 树哈希冲突处理：

   • 使用多重哈希减少冲突
   • 对于同构的子树，还要检查子树大小

2. 绿色候选生成：

   def find_green_candidates(u, parent):
       sizes = [1]
       for v in children[u]:
           if v != parent:
               child_sizes = find_green_candidates(v, u)
               new_sizes = []
               for s1 in sizes:
                   for s2 in child_sizes:
                       if s1 + s2 <= M:
                           new_sizes.append(s1 + s2)
               sizes = merge_sizes(sizes, new_sizes)
       return sizes
   

3. $D$ 的计数： 使用 Cayley 公式的变种，考虑子树大小约束。

总结

本题的核心在于：

1. 识别初始的绿色节点集合
2. 分析红色部分的结构特征
3. 计算满足约束的有根树 $D$ 的数量

通过树哈希、动态规划和组合计数技术的结合，可以系统性地解决这个复杂的树结构推断问题。