RT，运行如下代码：

int dfs(int u, int fa) {
	int now=1;
	f[u][0]=f[u][1]=0;
	for(int k=h[u];k;k=d[k].n) {
		int v=d[k].b, c=d[k].c;
		if(v==fa) continue;
		int tmp=dfs(v, u);
		for(int i=min(now+tmp,m);i>=2;i--) {
			for(int j=min(now,i);j>=1;j--) {
				cnt++;
				f[u][i]=min(f[u][i], f[u][j]+f[v][i-j]+c*(i-j)*(m-i+j));
			}
		}
		now+=tmp;
	}
	return now;
}

其中 $n\le1500$，$m\le1000$，运行完成后 $cnt$ 的值为 $45313030$。树形 dp 的复杂度不是 $O(nm)$ 的吗？求大神指点。