树结构中叶子节点移除唯一方式的枚举算法求解

首先明确核心规则：

• 仅能移除当前树中的叶子节点；
• 根节点仅当所有子节点都被移除（成为叶子）后才能被移除；
• 可以选择不进行任何移除操作。

一、计算合法剩余状态的数量 #

合法剩余状态指最终保留的节点集合，满足：若节点被保留，则其父节点必须被保留（否则父节点被移除的前提是所有子节点都被移除，矛盾）；但保留父节点时，可以选择移除其任意子节点（只要移除子节点时它是叶子）。

递推关系 #

定义cnt(u)为以u为根的子树的合法剩余状态数量：

1. 叶子节点：cnt(u) = 2（要么保留，要么移除）
2. 非叶子节点：假设u有k个子节点v₁, v₂, ..., vₖ，则

   cnt(u) = (cnt(v₁) × cnt(v₂) × ... × cnt(vₖ)) + 1
   

   解释：
   • 乘积项：保留u时，每个子树可以独立选择任意合法剩余状态，所有组合的总数；
   • +1：移除u的情况（必须先移除所有子树的所有节点，最终剩余空集）。

示例验证 #

假设根节点R有两个子节点A（含叶子子节点C）和B（叶子）：

• cnt(C)=2，cnt(A)=2+1=3，cnt(B)=2
• cnt(R)=3×2 +1=7，对应7种剩余状态：{R,A,C,B}, {R,A,C}, {R,A}, {R,B}, {R}, {R,A,B}, {}

二、计算合法操作序列的数量 #

操作序列指逐步移除叶子的过程（可随时停止），不同的移除顺序算不同的序列。

递推定义 #

定义：

• a(u)：以u为根的子树中，最终保留u的操作序列总数；
• b(u)：以u为根的子树中，最终移除u的操作序列总数；
• c(u) = a(u) + b(u)：以u为根的子树的总操作序列数。

递推关系 #

1. 叶子节点：

   • a(u)=1（直接不操作）
   • b(u)=1（仅移除u这一步）
   • c(u)=2

2. 非叶子节点：
   假设u有k个子节点v₁, ..., vₖ：

   • a(u)：合并所有子树的任意操作序列（保留或移除子树根）的所有可能交错方式总数；
   • b(u)：合并所有子树的移除序列（必须移除每个子树根）的所有可能交错方式，再加上最后一步移除u的操作总数。

   为了计算交错方式，需结合指数生成函数处理序列合并的组合数：

   • 定义节点x的指数生成函数E_x = sum (seq_count(l)/l! ) x^l，其中seq_count(l)是长度为l的序列数；
   • 保留u的生成函数：E_a(u) = product (E_a(v_i) + E_b(v_i))
   • 移除u的生成函数：E_b(u) = product(E_b(v_i)) × x
   • 总序列数为sum (l! × [x^l]E_a(u)) + sum (l! × [x^l]E_b(u))，即代入x=1后计算各阶乘系数之和。

示例验证 #

根节点R有两个叶子子节点A、B：

• a(A)=1, b(A)=1；a(B)=1, b(B)=1
• a(R)=5（对应序列：[], [移除A], [移除B], [移除A,移除B], [移除B,移除A]）
• b(R)=2（对应序列：[移除A,移除B,移除R], [移除B,移除A,移除R]）
• 总序列数5+2=7

三、枚举所有操作选项 #

枚举剩余状态 #

通过递归遍历每个节点：

1. 对于当前节点u，首先记录“保留u+所有子树的剩余状态组合”；
2. 再记录“移除u（即所有子树都移除至空集）”的状态。

枚举操作序列 #

通过递归生成所有可能的交错序列：

1. 对于当前节点u，生成所有子树的操作序列，然后合并这些序列的所有交错排列；
2. 对于移除u的情况，先生成所有子树的移除序列并合并，再追加移除u的步骤。

内容的提问来源于stack exchange，提问作者0x13