这只是代表我个人的一点观点，如有不对请指出。

简单看了一下题解，发现有相当一部分的题解的Sub1需要开O2才可以通过，因为他们写了 $O(n^3)$ 算法，这是不可以通过的，希望不要误导到刚刚学树形dp的同学。

而正确的写法可以参考如下代码：

#include<bits/stdc++.h>
#define int long long
#define MAXN 2001
using namespace std;

int n,k;
struct node{
	int to,x;
}; 
vector<node> e[MAXN];
int siz[MAXN],f[MAXN][MAXN];
void dfs(int x,int dad){
	siz[x]=1;
	f[x][0]=f[x][1]=0;
	int son=0;
	for(int i=0;i<e[x].size();i++){
		int to=e[x][i].to;
		if(to==dad)
			continue;
		dfs(to,x);
		son++;
		siz[x]+=siz[to]; 
	}
	if(son>1){
		for(int i=0;i<e[x].size();i++){
			int to=e[x][i].to;
			if(to==dad)
				continue;
			for(int v=min(siz[x],k);v>=0;v--){
				if(f[x][v]!=-1)
					f[x][v]+=siz[to]*(n-siz[to]-k)*e[x][i].x+f[to][0];
				for(int j=1;j<=min(siz[to],v);j++)
					if(f[x][v-j]!=-1) 
						f[x][v]=max(f[x][v],f[x][v-j]+f[to][j]+(siz[to]-j)*(n-siz[to]-k+j)*e[x][i].x+j*(k-j)*e[x][i].x);
			}
		}
	}
	else{
		for(int i=0;i<e[x].size();i++){
			int to=e[x][i].to;
			if(to==dad)
				continue;
			for(int v=0;v<=min(siz[x],k);v++){
				f[x][v]=f[to][v];
				if(f[x][v]!=-1)
					f[x][v]+=(siz[to]-v)*(n-siz[to]-k+v)*e[x][i].x+v*(k-v)*e[x][i].x;
			}
			for(int v=min(siz[x],k);v;v--)
				if(f[x][v-1]!=-1)
					f[x][v]=max(f[x][v],f[x][v-1]);
		}
	}
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back((node){v,w});
		e[v].push_back((node){u,w});
	}
	memset(f,-1,sizeof(f));
	dfs(1,-1);
	cout<<f[1][k];
	return 0;
}

当某个节点的儿子只有一个的时候，可以直接 $O(n)$ 转移，就避免了一条链的Hack了。

这个时候，我们算法在最坏的时候就是一颗完全二叉树。经过简单评估，这个算法在不考虑一个儿子节点 $O(n)$ 转移的情况下，时间复杂度是 $O(\sum siz_i^2)$ 。

这个时候，全部节点的子树平方和应该是 $\sum_{i=1}^{\log n} (2^{i})^2\times \dfrac {n}{2^i} = n\sum_{i=1}^{\log n} 2^i=n^2$ ，这样才是一个严格 $O(n^2)$ 的算法。