题解：P10092 [ROIR 2022 Day 2] 网络系统升级计划

Nygglatho · 2024-10-22 12:39:13 · 题解

这和吉林 CPC 的 B 题类似，考虑树形 DP。

令：

考虑当前节点 \mathit{now} 选择连向其儿子的边，如果选择了 (\mathit{now},v) 这条边，则 v 对 \mathit{dp}_\mathit{now} 的贡献为 dp_{v,1}+1。因为 v 连向其父亲节点也算作一条边。同样，v 对 \mathit{val}_{\mathit{now}} 的贡献为 \mathit{val}_{v,1}+d，其中 d 是该边的边权。而如果不选择这条边，则对 \mathit{dp}_{\mathit{now}} 的贡献为 dp_{v,0}，对 \mathit{val}_{\mathit{now}} 的贡献为 \mathit{val}_{v,0}。

显然你肯定要选择 \mathit{dp}_{v,1}+1-\mathit{dp}_{v,0} 尽量大的，如果相同就选择 \mathit{val}_{v,1}+d-\mathit{val}_{v,0}（d 为边权）尽量小的。这样可以保证答案尽量大。按照这种方式进行排序，然后直接选择即可。

int n, k;
ll val[310000][2], dp[310000][2];
ll a[310000];
vector <pii> v[310000];
vector <pii> _v;

void dfs (int now) {
    ll s0 = 0ll, s1 = 0ll;
    ll vl0 = 0ll, vl1 = 0ll;
    ll mx = 0ll, mn = 0ll;
    _v.clear();
    for (auto [i, j] : v[now]) dfs (i);
    for (auto [i, j] : v[now]) _v.push_back({i, j}), vl0 += val[i][0], s0 += dp[i][0];
    sort (_v.begin(), _v.end(), [] (pii X, pii Y) {
        auto [x, _] = X; auto [y, __] = Y;
        if (dp[x][1] - dp[x][0] == dp[y][1] - dp[y][0]) return (_ + val[x][1] - val[x][0] < __ + val[y][1] - val[y][0]);
        return (dp[x][1] - dp[x][0] > dp[y][1] - dp[y][0]);
    });
    mx = s0, mn = vl0;
    dp[now][0] = dp[now][1] = mx;
    val[now][0] = val[now][1] = mn;
    int cnt = 0;
    for (auto [i, j] : _v) {
        ++ cnt;
        s0 -= dp[i][0], s1 += dp[i][1] + 1;
        vl0 -= val[i][0], vl1 += val[i][1] + j;
        mx = s0 + s1, mn = vl0 + vl1;
        if (cnt <= k) {
            if (mx > dp[now][0]) {
                dp[now][0] = mx; val[now][0] = mn;
            } else if (mx == dp[now][0] && mn < val[now][0]) {
                val[now][0] = mn;
            }
        }

        if (cnt <= k - 1) {
            if (mx > dp[now][1]) {
                dp[now][1] = mx; val[now][1] = mn;
            } else if (mx == dp[now][1] && mn < val[now][1]) {
                val[now][1] = mn;
            }
        }
    }
    _v.clear();
}

int main() {
    cin >> n >> k;
    F (i, 2, n) {
        int p;
        cin >> p >> a[i];
        v[p].push_back({i, a[i]});
    }
    dfs (1);
    cout << dp[1][0] << ' ' << val[1][0] << '\n';
}