algorithm - 树的子树

Question

我有一棵具有 n 个节点的给定树。任务是找到给定树的出边到其补码的子树的数量小于或等于给定数 K。

例如:如果n=3且k=1

给定的树是1---2---3

那么总的有效子树将是 6

{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}

我知道我可以枚举所有 2^n 树并检查有效树，但是有没有更快的方法？我可以在 n 中实现多项式时间吗？接近 O(n^3) 甚至 O(n^4) 的东西会很好。

编辑:对于 k=1，这个值变成了 2*n

Answer 1

这是 DP-on-a-tree 范例的一个相当典型的实例。让我们通过允许指定根顶点 v 并以两种方式对小边界树的计数进行分层来稍微概括一下问题:是否包含 v，以及有多少条边组成边界。

基本情况很简单。没有边，因此有两个子树:一个包含 v，另一个不包含 v，并且都没有边界边。否则，设 e = {v, w} 是 v 的一条边。实例如下所示。

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

递归计算以 v 为根的 L 和以 w 为根的 R 的分层计数。

包含 v 的子树由 L 中包含 v 的子树、可选的 e 和 R 中包含 w 的子树组成。不包含 v 的子树由 L 中不包含 v 的子树或 R 中的子树组成(重复计算空树)。这意味着我们可以通过将 L 的分层计数与 R 的分层计数进行卷积来获得分层计数。

这是在您的示例中的工作原理。让我们选择根 1。

  e
1---2---3

如图所示，我们选择 e 并递归。

1

includes-1 的向量是 [1]，因为一个子树是 {1}，没有边界。 excludes-1 的向量是 [1]，因为一个子树是 {}，也没有边界。

2---3

我们像计算 1 一样计算 2 和 3。includes-2 的向量是 [1, 1]，因为 {2, 3} 没有边界边，而 {2} 有边界边。我们通过将 2 的 includes-2 向量添加到 2 的 includes-2 向量与 3 的 includes-3 向量的卷积中得到这个向量，由于新的边界边缘使 [0, 1] 移动 1 , 即 [1, 0]。 excludes-2 的向量是 [1] + [1, 1] - [1] = [1, 1]，其中 [1, 1] 是移位的 includes-3 向量和 excludes-3 向量的总和，减法是为了补偿重复计算 {}。

现在，对于原始调用，为了获得 includes-1 向量，我们将 [0, 1]，即 1 的 includes-1 向量加到 [1] 与 [1, 1] 的卷积中, 获得 [1, 2]。要检查:{1, 2, 3}没有边界，{1}和{1, 2}有一个边界边缘。 excludes-1 向量是 [1] + [1, 2, 1] - [1] = [1, 2, 1]。要检查:{} 没有边界，{2, 3} 和 {3} 有一个边界边，{2} 有两个边界边。