【悬关】选课（树上背包）加强版求调

#include <iostream>
#include <vector>

using namespace std;

const int N = 100000, M = 100000, NM = 1e8;
int n, m, s[N + 5], siz[N + 5], f[NM + N + M + 5];
vector<int> e[N + 5];

void calc(int u)
{
    for (auto v : e[u])
    {
        calc(v);
        // 目前 siz[u] 记录已合并的子树的大小的和
        for (int i = min(m, siz[u] + siz[v]); i >= 1; i--)             // 把目前所有子树都选上也只有 siz[u] + siz[v] 个
            for (int j = max(i - siz[u], 0); j <= min(i, siz[v]); j++) // 子树 v 中至少选 i - siz[u] 个，不然达不到选 i 个；全选是 siz[v] 个，不可能更多
                // f[u][i] = max(f[u][i], f[u][i - j] + f[v][j]);
                f[u * (m + 1) + i] = max(f[u * (m + 1) + i], f[u * (m + 1) + i - j] + f[v * (m + 1) + j]);
        siz[u] += siz[v];
    }
    siz[u]++;   // 加上 u 本身
    if (u != 0) // 子树合并的时候没有考虑选 u 本身，如果 u 不是虚拟根结点 0 那么就必须选 u 本身
        for (int i = siz[u]; i >= 1; i--)
            // f[u][i] = f[u][i - 1] + s[u];
            f[u * (m + 1) + i] = f[u * (m + 1) + i - 1] + s[u];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k >> s[i];
        e[k].push_back(i);
    }
    calc(0);
    cout << f[m] << "\n";

    return 0;
}