title: Subtrees of a tree
body: <p>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.</p>
  
  <p>for example: If <code>n=3</code> and <code>k=1</code></p>
  
  <p>and the given tree is    <code>1---2---3</code></p>
  
  <p>Then the total valid subtrees would be 6</p>
  
  <pre><code>{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}
  </code></pre>
  
  <p>I know I can enumerate all <code>2^n</code> trees and chack the valid ones, but is there some approach that is faster? Can I achieve polynomial time in <code>n</code>? Something close to <code>O(n^3)</code> or even <code>O(n^4)</code> would be nice.</p>
  
  <p>EDIT: for k=1 this value turns out to be <code>2*n</code></p>