Tree subtrees

Question

I have a given tree with n nodes. The task is to find the number of subtrees of a given tree with outgoing edges in its complement, less than or equal to a given number K.

for example: If n=3 and k=1

and this tree 1---2---3

Then the total valid subtrees will be 6

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

I know that I can list all 2^n trees and check for valid ones, but is there some kind of approach that is faster? Can I reach polynomial time in n ? Something close to O(n^3) or even O(n^4) would be nice.

EDIT: for k = 1, this value is 2*n

Answer 1

Here is my python implementation of David Eisenstat's solution:

 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 

Answer 2

This is a fairly typical example of the DP-on-tree paradigm. Let me generalize the problem a bit by resolving the specification of the root vertex v and stratifying the calculations of small boundaries in two ways: whether v is inclusive and how many edges the boundary contains.

The base case is simple. There are no edges and, therefore, two subtrees: one includes v, the other excludes v, and both have no boundaries. Otherwise, let e = {v, w} be the edge incident to v. The instance is as follows.

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

Calculate the recursively stratified counts for L embedded in v and R embedded in w.

Subdirs containing v consist of a subtree in L, which includes v, plus optionally e, and a subtree in R, which includes w. Subtrees that do not include v consist of either a subtree in L that does not include v or a subtree in R (double counting an empty tree). This means that we can get stratified counts by convolving stratified counts for L with stratified counts for R.

Here's how it works in your example. Choose root 1.

  e 1---2---3 

We choose e, as shown and recursively.

 1 

The vector for include-1 is [1], since one subtree is {1}, without a border. The vector for exceptions-1 is [1], since one subtree {} also has no boundary.

 2---3 

We calculate 2 and 3, as in case 1. The vector for inclusion-2 is [1, 1], since {2, 3} has no boundary edges, and {2} has one. We got this vector by adding the inclusion vector-2 for 2, shifted by one due to the new boundary edge, to make [0, 1], the convolution of the inclusion vector-2 for 2 with the inclusion vector-3 for 3, which is [1 , 0]. The vector for exceptions-2 is [1] + [1, 1] - [1] = [1, 1], where [1, 1] is the sum of the shifted vector of include-3 and the vector of exceptions-3, and the subtraction should compensate double counting {}.

Now, for the original call, to get the vector include-1, add [0, 1], including-1 vector for 1 shifted by one, to convolution [1] with [1, 1], getting [1, 2]. To check: {1, 2, 3} has no boundary, and {1} and {1, 2} have one boundary edge. The vector of exceptions-1 is [1] + [1, 2, 1] - [1] = [1, 2, 1]. To check: {} has no boundary, {2, 3} and {3} have one boundary edge, and {2} has two boundary edges.