题目
 题解
这里证明一下复杂度

1.数学证法

$S_{u}$ 表示 $u$ 的子树大小
这里只考虑大小的级别，常数就不考虑了
$T = \sum_{u} \sum_{f a_{i} = u, f a_{j} = u} S_{i} S_{j}$
$= \sum_{u} [(\sum_{f a_{i} = u} S_{i})^{2} - \sum_{f a_{i} = u} S_{i}^{2}]$
$= \sum_{u} S_{u}^{2} - \sum_{u} \sum_{f a_{i} = u} S_{i}^{2}$
考虑到每个点只有一个父亲，所以：
$\sum_{u} \sum_{f a_{i} = u} S_{i}^{2} = \sum S_{i}^{2}$
$T = O (n^{2})$

2.理论证法

这个算法看作枚举每个点，统计以它作为 $l c a$ 的点对个数，然后这些值全加起来
本质上就是求点对的个数，而点对个数是 $O (n^{2})$ 的，所以这个算法复杂度也是 $O (n^{2})$ 的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7,N=2002;
struct node{
	int to,ne;
}e[N<<1];
int tot,h[N],f[N][N],s[N],i,n,k,x,y;
void add(int x,int y){
	e[++tot]=(node){y,h[x]};
	h[x]=tot;
}
void dfs(int u,int fa){
	f[u][s[u]=1]=1;
	for (int t=h[u],v;t;t=e[t].ne)
		if ((v=e[t].to)!=fa){
			dfs(v,u);
			for (int i=s[u];i;i--){
				for (int j=s[v];j;j--) (f[u][i+j]+=(ll)f[u][i]*f[v][j]%M)%=M;
				f[u][i]=(ll)f[u][i]*f[v][0]%M;
			}
			s[u]+=s[v];
		}
	for (int i=k;i<=s[u];i++) (f[u][0]+=f[u][i])%=M;
}
int main(){
	scanf("%d%d",&n,&k);
	for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1,0);
	printf("%d",f[1][0]);
}

51nod 1353 树

1.数学证法

2.理论证法