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.
for example: If n=3 and k=1
and the given tree is 1---2---3
Then the total valid subtrees would be 6
{}, {1}, {3}, {1,2}, {2,3}, {1,2,3}
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.
for k=1 this value turns out to be 2*n
Here is a link to the problem statement