我有一个带有 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
问问题
3029 次
3 回答
3
这是一个相当典型的 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
include-1 的向量是 [1]，因为一个子树是 {1}，没有边界。excludes-1 的向量是 [1]，因为一个子树是 {}，也没有边界。
2---3
我们像计算 1 一样计算 2 和 3。includes-2 的向量是 [1, 1]，因为 {2, 3} 没有边界边，而 {2} 有一个。我们通过将 2 的包含 2 向量（由于新的边界边缘而移动 1 以形成 [0, 1]）添加到 2 的包含 2 向量与 3 的包含 3 向量的卷积来获得该向量，即 [1, 0]。excludes-2 的向量是 [1] + [1, 1] - [1] = [1, 1]，其中 [1, 1] 是移位的 includes-3 向量和 excludes-3 向量的和，减法是为了补偿重复计算{}。
现在，对于原始调用，为了获得 includes-1 向量，我们将 [0, 1]，即 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} 有两个边界边。
于 2013-06-01T12:53:02.213 回答
2
这是我对 David Eisenstat 解决方案的 python 实现：
from sys import stdin
from numpy import *
from scipy import *
def roundup_pow2(x):
"""
Round up to power of 2 (obfuscated and unintentionally faster :).
"""
while x&(x-1):
x = (x|(x>>1))+1
return max(x,1)
def to_long(x):
return long(rint(x))
def poly_mul(a,b):
n = len(a) + len(b) - 1
nr = roundup_pow2(n)
a += [0L]*(nr-len(a))
b += [0L]*(nr-len(b)) # pad with zeros to length n
u = fft(a)
v = fft(b)
w = ifft(u*v)[:n].real # ifft == inverse fft
return map(to_long,w)
def pad(l,s) :
return l+[0L]*(s-len(l))
def make_tree(l,x,y):
l[x][y]=y
l[x].pop(y)
for child in l[x]:
make_tree(l,child,x)
def cut_tree(l,x) :
if len(l[x])==0:
return [1L],[1L]
y,_ = l[x].popitem()
ai,ax=cut_tree(l,x)
bi,bx=cut_tree(l,y)
ci=[0L]+ai
tmp=poly_mul(ai,bi)
padlen=max(len(ci),len(tmp))
ci=pad(ci,padlen)
tmp=pad(tmp,padlen)
ci=map(add,ci,tmp)
cx=[0L]+bi
padlen=max(len(cx),len(bx),len(ax))
cx=pad(cx,padlen)
bx=pad(bx,padlen)
ax=pad(ax,padlen)
tmp=pad([-1],padlen)
cx=map(add,cx,bx)
cx=map(add,cx,ax)
cx=map(add,cx,tmp)
return ci,cx
n,k = map(int,raw_input().split())
l=[{}]
for i in range(1,n+1):
d={}
l.append(d)
for i in range(1,n):
x,y = map(int,raw_input().split())
l[x][y]=y
l[y][x]=x
make_tree(l,1,0)
i,x = cut_tree(l,1)
padlen=max(len(i),len(x))
i=pad(i,padlen)
x=pad(x,padlen)
combined=map(add,i,x)
sum=0L
for i in range(0,k+1) :
sum+=combined[i]
print sum
于 2013-07-09T19:09:02.547 回答
0
让我们创建一个稍大的树，如下所示。
1
/ | \
2 3 \
/ 4
7 / \
5 6
让我们为每个节点 'a' 定义一个函数 F(a, k)，并从节点 'a' 及以下移除 'k' 条边。即，如果从节点“a”中删除“k”条边，则我们创建 F(a,k) 个子树。（如果“a”不是根，则假定它连接到它的父级）。
例如在上面的树（ F(4, 1) = 2 ）中，因为我们通过删除 '4' 下面的 2 条边来创建 2 棵树（我们假设 4 连接到父树并且子树 (5) 和 (6) 不计入F(4,1))
我们首先遍历并计算每个孩子的'F'。然后使用孩子的 F 我们计算父母 F。
对于所有 k，叶节点的 F(a, k) 为 '0'
对于非叶节点。
F(a, k) = SUM (F(child, k)) + Z
而 F(child, k) 可以递归计算。
另一方面，Z 是通过查找所有组合来计算的，其中一些孩子从 k 中取出 ri 边，使得 SUM(ri) = k
以编程方式，这可以通过固定给定孩子的“j”边然后计算通过将“kj”边分配给其他孩子而创建的树的数量来完成。
例如在上面的树中
F(1, 3) = F(2, 3) + F(3, 3) + F(4, 3) + // we pass k as-is to child
F(2,1)*F(3,1)*F(4,1) + F(2,1)*F(3,2) + F(2,1)*F(4,2) + //consume 1 edge by 2 and distribute 2 to other children
F(2, 2)*F(3,1) + F(2,2)*F(4,1) + // consume 2 edges from node '2' and 1 for other children
F(3,1)*F(4,2)
正如我们在上面看到的，我们为节点 2 固定“r”边，然后将“3-r”边分配给其他子节点。我们继续为“1”的所有孩子这样做。
此外，当我们从父节点分离节点时，我们会创建子树。例如，在上述情况下，当我们计算 F(1, 3) 时，我们会创建以下分离树。detached_tree += F(2, 2) + F(3, 2) + F(4, 2)
这里我们假设一条边通过从父节点分离子节点被消耗，如果我们消耗'k-1'则在子节点我们将创建 F(child, k-1) 个子树。这些树被计算并单独存储在 detached_trees 中。
一旦我们计算了所有节点的 F(a,k)。
所有 k 的子树总数为 'SUM(F(root, k))' + 'total nodes - 1' + detached_trees。
我们将“总节点 - 1”添加到我们的总数中。这是因为当一个节点（除了根节点）从一棵树中分离出来时，它会创建两棵缺少 1 条边的树。虽然其中一棵树被计算在 F(parent, 1) 中，但另一棵树在任何地方都没有计算在内，因此需要总计计算。
这是上述算法的C代码。递归可以进一步优化。
#define MAX 51
/* We use the last entry of alist to store number of children of a given node */
#define NUM_CHILD(alist, node) (alist[node][MAX])
int alist[MAX][MAX+1] = {0};
long F[MAX][MAX]={0};
long detached_subtrees = 0;
/*
* We fix one of the child node for 'i' edges out of 'n', then we traverse
* over the rest of the children to get 'n-i' edges, we do so recursivly.
* Note that if 'n' is 1, we can always build a subtree by detaching.
*/
long REST_OF_NODES_SUM(int node, int q, int n)
{
long sum = 0, i, node2, ret = 0, nd;
/* fix node2 and calcualte the subtree for rest of the children */
for(nd = q; nd < NUM_CHILD(alist, node); nd++) {
node2 = alist[node][nd];
/* Consume 'i' edges and send 'n-i' for other children of node */
for (i = 1; i < n ; i++) {
sum = REST_OF_NODES_SUM(node, nd + 1, n - i);
ret += (F[node2][i] * sum);
/* Add one for 'node2' getting detached from tree */
if (i == 1) { ret += sum; }
}
ret += F[node2][n];
/* If only one edge is to be consumed, we detach 'node2' from the tree */
if (n == 1) { ret++; }
}
return ret;
}
void get_counts(int N, int K, int node, int root)
{
int child_node;
int i, j, p, k;
if (NUM_CHILD(alist, node) == 0) { return; }
for(i = 0 ; i < NUM_CHILD(alist, node); i++) {
child_node = alist[node][i];
/* Do a recursive traversal of all children */
get_counts(N, K, child_node, node);
F[node][1] += (F[child_node][1]);
}
F[node][1] += NUM_CHILD(alist, node);
for (k = 2; k <= K; k++) {
for(p = 0; p < NUM_CHILD(alist, node); p++) {
child_node = alist[node][p];
F[node][k] += F[child_node][k];
/* If we remove this child, then we create subtrees in the child */
detached_subtrees += F[child_node][k-1];
/* Assume that 'child_node' is detached, find tree created by rest
* of children for 'k-j' edges */
F[node][k] += REST_OF_NODES_SUM(node, p + 1, k - 1);
/* Fix one child node for 'j' edges out of 'k' and traverse over the rest of
* children for 'k - j' edges */
for (j = 1; j < k ; j++) {
if (F[child_node][j]) F[node][k] += (F[child_node][j] * REST_OF_NODES_SUM(node, p + 1, k - j));
}
}
}
}
void remove_back_ref(int parent, int node)
{
int c;
for (c = 0; c < NUM_CHILD(alist, node); c++) {
if (alist[node][c] == parent) {
if ((c + 1) == NUM_CHILD(alist, node)) {
NUM_CHILD(alist, node)--;
alist[node][c] = 0;
} else {
/* move last entry here */
alist[node][c] = alist[node][NUM_CHILD(alist, node)-1];
alist[node][NUM_CHILD(alist, node)-1] = 0;
NUM_CHILD(alist, node)--;
}
}
}
}
/* go to each child and remove back links */
void normalize(int node)
{
int j, child;
for (j = 0; j < NUM_CHILD(alist, node); j++) {
child = alist[node][j];
remove_back_ref(node, child);
normalize(child);
}
}
long cutTree(int N, int K, int edges_rows, int edges_columns, int** edges)
{
int i, j;
int node, index;
long ret = 0;
/* build an adjacency list from the above edges */
for (i = 0; i < edges_rows; i++) {
alist[edges[i][0]][NUM_CHILD(alist, edges[i][0])] = edges[i][1];
alist[edges[i][1]][NUM_CHILD(alist, edges[i][1])] = edges[i][0];
NUM_CHILD(alist, edges[i][0])++;
NUM_CHILD(alist, edges[i][1])++;
}
/* get rid of the back links in children */
normalize(1);
get_counts(N, K, 1, 1);
for (i = 1; i <= K; i++) { ret += F[1][i]; }
/* Every node (except root) when detached from tree, will create one extra subtree. */
ret += (N - 1);
/* The subtrees created by detaching from parent */
ret += detached_subtrees;
/* Add two for empty and full tree */
ret += 2;
return ret;
}
main(int argc, char *argv[])
{
int **arr;
int ret, i, N, K, x, y;
scanf("%d%d", &N, &K);
arr = malloc((N - 1) * sizeof(int*));
for (i = 0; i < (N - 1); i++) { arr[i] = malloc(2*sizeof(int)); }
for (i = 0; i < N-1; i++) { scanf("%d%d", &x, &y); arr[i][0] = x; arr[i][1] = y; }
printf("MAX %d ret %ld\n", MAX, cutTree(N, K, N-1, 2, arr));
}
于 2018-07-27T13:49:05.457 回答