Welcome to the Internet. What would you prefer?

前言：今天 T1 数据也太水了。

void dfs(int u, int fa, int l) {
	siz[u] = 1;
	tsum[u] = a[u];
	f[u][0] = l * abs(a[u] - x);
	f[u][1] = l * abs(a[u] - y);
	for (const auto &i : e[u]) {
		int v = i.first, w = i.second;
		if (v == fa) continue;
		dfs(v, u, w);
		for (int i = min(siz[u] + siz[v], m); ~i; i--) {
			res[i] = 1e18;
			for (int j = 0; j <= min(siz[v], i); j++)
				res[i] = min(res[i], f[u][i - j] + f[v][j] - l * abs(tsum[u] - y * (i - j) - x * (siz[u] - (i - j))) + l * abs(tsum[u] + tsum[v] - y * i - x * (siz[u] + siz[v] - i)));
		}
		for (int i = min(siz[u] + siz[v], m); ~i; i--) f[u][i] = res[i];
		siz[u] += siz[v];
		tsum[u] += tsum[v];
	}
}

首先是一个很正常的树上背包，应该都看得出来。

这是过不了我随便随机的一组极限数据的，但是能在 OJ 上 A。

原因是它退化到了 \(O(nm ^ 2)\)。

为什么呢？感觉没有什么问题啊？

其实还是没有排除完冗余情况。

因为要保证 \(i - j \leq siz_u\)，所以 \(j\) 的下界应该是 \(\max(0, i - siz_u)\)。这样就可以过了。

还是要尤其注意，，，复杂度证明：Link。

本来以为可以探究点什么，没想到单纯是约束少了，，，

以及数据在这里：Link。