Let us create a slightly bigger tree like below.
1
/ | \
2 3 \
/ 4
7 / \
5 6
Let us define a function F(a, k) for each node 'a' with 'k' edges removed from node 'a' and below.
i.e. if 'k' edges are removed from node 'a' then we create F(a, k) number of subtrees.
(If 'a' is not root, it is assumed to be connected to it's parent).
e.g. in above tree ( F(4, 1) = 2 ), as we create 2 trees by removing 2 edges below '4'
(we assume that 4 is connected to parent and subtrees (5) and (6) are not counted in F(4,1))
We traverse and calculate 'F' of each child first. Then using child's F we calculate
parents F.
F(a, k) of a leaf node is '0' for all k
For non-leaf nodes.
F(a, k) = SUM (F(child, k)) + Z
While F(child, k) can be calculated recursively.
Z on the other hand is calculated by finding all combinations where some child take
ri edges out of k such that SUM(ri) = k
Programmatically this can be done by fixing 'j' edge for a given child and then
calculating the number of trees created by distributing 'k-j' edges to other children.
e.g. in above tree
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)
As we see above, we fix 'r' edge for node 2 and then distribute '3-r' edges to other children.
We keep doing this for all children of '1'.
Additionally, we create sub-trees when we detach a node from parent.
e.g. in above case when we calculate F(1, 3) we create the following
detached trees.
detached_tree += F(2, 2) + F(3, 2) + F(4, 2)
Here we assume that one edge is consumed by detaching child node from parent,
and in child node if we consume 'k-1' edges we will create F(child, k-1) subtrees.
These trees are counted and stored seperately in detached_trees.
Once we have calculated the F(a,k) of all nodes.
The total subtrees are 'SUM(F(root, k)) for all k' + 'total nodes - 1' + detached_trees.
We add 'total nodes - 1' to our total. This is because when a node (except root) is detached
from a tree, it creates two trees with 1 edge missing. While one of the tree is counted
in F(parent, 1), the other is not counted anywhere, hence needs to be counted in total.
Here is C code of above algorithm. The recursion can be further optimized.
#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));
}
