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;
}
}