给定一棵有N个结点的二叉树。求它的所有结点数为M的连通子图数目。
设以n为根的结点数为m的连通子图数目 dp[n][m]
dp[n][m] =
dp[2n][m-1] //左孩子
+dp[2n+1][m-1] //右孩子
+SUM { dp[2n][i] * dp[2n+1][m-1-i]} //1<=i<m-1 左边有i个结点,右边有m-1-i个
input:
one tree
m
output:
SUM (dp[i][m]) //i=1...n