求问这样子写的原因
查看原帖
求问这样子写的原因
381949
Federico2903楼主2024/4/19 18:43

rt,如下树形 dp 两种写法的区别是什么。

void dp(int u, int fa) {
	siz[u] = (u <= n);
	int ch0 = 0, ch1 = 0;
	for (auto v : T[u]) {
		if (v == fa) continue;
		dp(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[ch0]) ch1 = ch0, ch0 = v;
		else if (siz[v] > siz[ch1]) ch1 = v;
	}
	f[u] = f[ch0];
	hs[u] = ch0;
	int ans0 = (u <= n), ans1 = (u <= n);
	for (auto v : T[u]) {
		if (v == fa || v == ch0) continue;
		if (u <= n) ans0 += siz[v];
		else ans0 = max(ans0, siz[v]);
		if (v == ch1) continue;
		if (u <= n) ans1 += siz[v];
		else ans1 = max(ans1, siz[v]);
	}
	if (u <= n) ans1 += n - siz[u];
	else ans1 = max(ans1, n - siz[u]);
	ans1 = max(ans1, f[ch0]);
	ans1 = max(ans1, f[ch1]);
	f[u] = max(f[u], ans0);
	if (ans1 <= ans) {    //正确
	//if (ans1 < ans) {   //错误
		ans = ans1, ps = u;
		p0 = ch0, p1 = ch1;
	}
}
2024/4/19 18:43
加载中...