枚举从树上移除叶子的独特方法的算法？

Question

我正在关注这个挑战：

考虑一个树形图，其中每个顶点只有当它是叶节点时才可以被删除。一个父节点可以有多个子节点。给定一个根节点，正如规则所暗示的，只有当其所有子树都被删除时才能删除该根节点。还可以选择不删除任何节点。有向边 (𝑢,𝑣) 表示 𝑢 是 𝑣 的父级。该算法应该返回给定树的此类选项的数量以及选项本身。

我试图为其找到一些最佳的子结构，但我找不到。叶子提供了 2^𝑛 选项，我们可以选择删除或不删除它们。如果一个节点有 m 个子节点，那么它将 𝑚2^𝑛−1+1 添加到上一层的选择计数中，几乎，我找不到正确的关系。

Answer 1

你应该期待的结构是这样的。假设节点

N

有子节点

C1, C2, ..., Cn

。还假设

options(node)

是从

node

中删除的方法有多少种。

然后

options(N) = options(C1) * options(C2) * ... * options(Cn) + 1

。为什么？第一项是因为您可以独立选择删除每个子项下面的任何方式。然后

+1

因为您可以删除整个子树，包括

N

本身。

要实际生成它们，只需迭代每个子选项的乘积，然后包含“所有内容”。