for(int i = head[u]; i; i = nxt[i]) {
	if(to[i] == fa)continue;
	dfs(to[i], u);
	sz[u] += sz[to[i]];
	for(int j = sz[u]; j >= 0; j--) {
		for(int k = 1; k <= min(j, sz[to[i]]); k++) {
			dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[to[i]][k]);
		}
	}
}

这样链的数据会卡成 $O(nm^2)$。

正确的写法是：

for(int i = head[u]; i; i = nxt[i]) {
	if(to[i] == fa)continue;
	dfs(to[i], u);
	for(int j = sz[u]; j >= 0; j--) {
		for(int k = 1; k <= sz[to[i]]; k++) {
			dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[to[i]][k]);
		}
	}
	sz[u] += sz[to[i]];
}

我感觉我学到现在看到的所有板子都是上面那种的（