本题是典型的树上背包，正确的算法复杂度是$O(nk)$，其中$n$是树的大小，$k$是可选的物品数量。subtask1是用来卡$O(n^3)$的错误写法的（不开O2的情况下）。在我正确通过了subtask1之后，我终于想通了为啥以及如何正确地做上下界优化，特发此贴以帮助后面卡在这里的人思考。

正如很多别的复杂度分析的文章指出，只要单个子树的算法复杂度是$O(n^2)$的，那么在dp数组限制上界到$k$之后，整体算法复杂度就是$O(nk)$。这一点不再赘述。本贴核心在于怎么控制子树复杂度到$O(n^2)$。

暂且不考虑dp数组上界控制到$k$的优化。每个子树的dp数组上界开到$n_i$，即该子树大小；于是，$n=\sum_{i=1}^kn_i$。设对大小为$n$的树复杂度是$T(n)$，那么应该有$T(n)=\sum_{i=1}^kT(n_i)+M(n_1,\cdots,n_k)$，其中$M(\cdot)$是合并步的复杂度。

一种（可能）正确的写法如下。

int sz = 1;
for (const auto& [nt, w]: gr[cr]) {
	if (nt==pa) continue;
	auto [cnt, ndp] = dfs(dfs, nt, cr);
	for (int i = min(sz+cnt, k); i>=0; --i) {
		for (int j = max(0, i-min(sz, k)); j<cnt && j<=i; ++j) {
			dp[i] = max(dp[i], dp[i-j]+ndp[j]+1LL*w*(j*(k-j)+(cnt-j)*(n-cnt-k+j)));
		}
	}
}

为什么这样是对的？因为（继续忽略$k$）我们需要把循环控制在$\{(i,j):0\le i\le sz+cnt,\max\{0,i-sz\}\le j\le \min\{cnt,i\}\}$内，这是一个平行四边形（请自行画图），所以总的大小是$(1+sz)(1+cnt)\le(1+n_i)(1+\sum_{j=1}^{i-1}n_j)$。适当牺牲严谨性但便于表达，扔掉括号里的$1$，这样只会扩大后面大O里的系数。那么，可归纳证明$T(n)\le n^2$。因为，$T(n)\le\sum_{i=1}^kT(n_i)+\sum_{i=1}^kn_i\sum_{j=1}^{i-1}n_j<=\sum_{i=1}^kn_i^2+2\sum_{i=1}^k\sum_{j=1}^{i-1}n_in_j=n^2$。在加上一堆一次项和常数项后，不会改变这个阶的判断。

一个常见的错误写法如下：

int sz = 1;
for (const auto& [nt, w]: gr[cr]) {
	if (nt==pa) continue;
	auto [cnt, ndp] = dfs(dfs, nt, cr);
	for (int i = min(sz+cnt, k); i>=0; --i) {
		for (int j = 0; j<cnt && j<=i; ++j) {
			dp[i] = max(dp[i], dp[i-j]+ndp[j]+1LL*w*(j*(k-j)+(cnt-j)*(n-cnt-k+j)));
		}
	}
}

它丢掉了j的下界控制。这样会给上面的平行四边形加个小三角，变成一个梯形。这个小小的三角形看似并没有改变合并步的复杂度，但是确实给整体复杂度提升了一个阶。此时算法复杂度大致是$T(n)=\sum_{i=1}^kT(n_i)+n^2/2$。如果树大致是平衡的，那么可以参考主定理，整体算法仍然是$O(n^2)$的。但是，对于极度不平衡的树，比如一个链，算法复杂度将满足$T(n)=T(n-1)+T(1)+n^2/2$，此时必然有$T(n)=\Theta(n^3)$，将完全无法接受。

所以请控制好上下界。