自动搬运

查看原文

来自洛谷，原作者为

	Nygglatho AFOed

搬运于2025-08-24 22:54:35，当前版本为作者最后更新于2024-10-22 12:39:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

令：

• $\mathit{dp}_{x,0}$ 表示节点 $x$ 选最多 $k$ 条边，以其为根的子树选择的边数最大值，$\mathit{val}_{x,0}$ 表示在 $\mathit{dp}_{x,0}$ 最大情况需要的最小成本。
• $\mathit{dp}_{x,1}$ 和 $\mathit{dp}_{x,0}$ 其他一样，但是只能选择最多 $k-1$ 条边，$\mathit{val}_{x,1}$ 表示在 $\mathit{dp}_{x,1}$ 最大情况需要的最小成本。

考虑当前节点 $\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';
}