树子树 [英] Subtrees of a tree

问题描述

我有n个节点给定的树。的任务是找到出边到其互补小于或等于给定数K

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

例如：如果 N = 3 和 K = 1

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

那么，总有效的子树将是6

Then the total valid subtrees would be 6

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

我知道我可以列举所有 2的n次方树和CHACK有效的，但有一些方法，是更快？我可以实现多项式时间 N ？一些接近为O（n ^ 3）甚至为O（n ^ 4）将是很好的。

I know I can enumerate all 2^n trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in n? Something close to O(n^3) or even O(n^4) would be nice.

编辑：对于k = 1这个值被证明是 2 * N

for k=1 this value turns out to be 2*n

推荐答案

下面是我的Python实现大卫Eisenstat的解决方案：

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

这篇关于树子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！