今天小a在纸上研究树的形态，众所周知的，有芭蕉树，樟树，函树，平衡树，树套树等等。那么小a今天在研究的就是其中的平衡树啦。
小a认为一棵平衡树的定义为一个n个点，从1到n编号，n-1条边，且任意两点间一定存在唯一一条简单路径，且n>=k。
现在小a看到一棵很大很大的树，足足有n个节点，这里n一定大于等于k！为了方便起见，它想把这个树删去某些边，使得剩下的若干个联通块都满足是平衡树。这时，小b走过来，不屑一顾的说，如果我一条边都不删，那么也算一棵平衡树咯。
小a对于小b的不屑感到很不爽，并问小b，你能算出我删边的方案总数使得满足我的条件吗？两个删边的方案A,B不同当且仅当存在某一条边属于集合A且不属于集合B，或者存在某一条边属于集合B且不属于集合A。为了让你方便，你只要告诉我答案对1000000007(1e9+7)取模就行了。
小b犯了难，找到了身为程序猿的你。
Hint:
样例解释，
第一种方案为不删边，
第二种方案为删去2 3这一条边，
第三种方案为删去3 4这一条边。
Input
第一行读入两个正整数n，k(1<=k<=n<=2000)。
接下来n-1行，每行两个正整数A,B ( 1<= A,B<= n)，表示A与B有一条边相连，题目保证在不删任何一条边的情况下是一棵平衡树。
Output
一个整数，表示答案对1000000007(1e9+7)取模后的值。
Input示例
5 2
1 2
2 3
3 4
4 5
Output示例
3
思路：树形DP
dp[i][j] 表示以i为根的子树 当前联通块大小为j 其他联通块都合法的方案数
用dp[i][0] 表示以i为根的子树有多少合法的方案
枚举u的每一个子节点 v 得到转移方程 dp[u][i+j]=Σdp[u][i]*dp[v][j]
另外dp[u][0]=Σdp[u][j](j>=题目给定的k)
这样乍看是n^3的，有一个技巧可以做到n^2即每次dp时，
只枚举当前u所在子树的大小，每当枚举到它的其中孩子时，
当前u所在子树的大小加上它孩子为根的子树的大小。可以理解为每一个点对只被枚举到一次。
最后答案即为dp[root][0]
1 #include <cstdio> 2 #include <cctype> 3 #include <vector> 4 5 typedef long long LL; 6 7 const int Mod=1000000007; 8 const int MAXN=5010; 9 10 int n,k; 11 12 int siz[MAXN]; 13 14 int dp[MAXN][MAXN]; 15 16 std::vector<int> Graph[MAXN]; 17 18 inline void read(int&x) { 19 int f=1;register char c=getchar(); 20 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 21 for(;isdigit(c);x=x*10+c-48,c=getchar()); 22 x=x*f; 23 } 24 25 void DFS(int u,int fa) { 26 dp[u][1]=1; 27 siz[u]=1; 28 29 for(int i=0; i<Graph[u].size(); ++i) { 30 int v=Graph[u][i]; 31 if(v==fa) continue; 32 DFS(v,u); 33 for(int i=siz[u]; i; --i) { 34 for(int j=1; j<=siz[v]; ++j) 35 dp[u][i+j]=(dp[u][i+j]+(LL)dp[u][i]*dp[v][j]%Mod)%Mod; 36 dp[u][i]=(LL)dp[u][i]*dp[v][0]%Mod; 37 } 38 siz[u]+=siz[v]; 39 } 40 for(int i=k; i<=siz[u]; ++i) dp[u][0]=(dp[u][0]+dp[u][i])%Mod; 41 } 42 43 int hh() { 44 read(n);read(k); 45 46 for(int x,y,i=1;i<n;++i) { 47 read(x);read(y); 48 Graph[x].push_back(y); 49 Graph[y].push_back(x); 50 } 51 52 DFS(1,-1); 53 54 printf("%d ",dp[1][0]); 55 56 return 0; 57 } 58 59 int sb=hh(); 60 int main(int argc,char**argv) {;}