以下是 P1273 有线电视网 的树上背包 dp 转移代码。

int dfs(int u) {
	dp[u][0] = 0, dp[u][1] = c[u];
	int f = (u > n - m); // f 表示 u 的子树中叶节点的数量 
	for (int i = hd[u]; i; i = e[i].nx) {
		int v = e[i].to, w = e[i].w;
		int t = dfs(v); f += t;
		for (int j = f; j >= 1; j --) {
			for (int k = 1; k <= t; k ++) {
				dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
			}
		}
	}
	return f;
}

乍一看，这份代码的时间复杂度是 $O(n^3)$ 的，但实际却跑得很快。

参见 帖1 和 帖2，这份代码即帖1中提到的“填表法”，我在本机使用楼主的数据生成器生成的数据跑了2.5s+，而用帖中“刷表法”的第一篇题解（现在是第二篇了，link）的代码确实跑得飞快（0.06s）。

关于时间复杂度的分析，两个帖子中均有回复提到：

任意两点只会在$lca$处贡献1的复杂度

点对只会在lca处被合并一次

然而两种优化方式的区别，以及正确复杂度为 $O(n^2)$ 的原因蒟蒻仍并不是很理解。

希望有大佬能够给出比较详细的解答。