题解：P14471 [集训队互测 2025] 火花

· · 题解

深刻。美味题。

分析

因为限制与祖先有关，不难想到在 dfs 序上做。

把回溯点也放进去，得到一个长度为 2n 的 dfs 序。记 u 先后出现的位置为 in_u,out_u；p_i 为 dfs 序中位置 i 表示的点。

这样可以定义状态函数 f_{i}(j,*) 表示考虑到 dfs 序中第 i 个位置，且 u\in P(fa_{p_i},1) 都在第二步被取了至少一个物品，一共取了 j 个物品的最大价值。

棘手的地方在于，第一步选择的点会影响它所有祖先的物品数量。

对于每个 u，在位置 out_u 决策是否在第一步选择它。记 s(i) 为 dfs 序中前 i 个位置被决策选择的点数量。那么对于一个 u，它子树（包括自己）中第一步被选择的点数量就是 s(out_u) - s(in_u)。此时 u 剩余物品数量为 (c_u -s(out_u)) + s(in_u) 。

因为 s(i) \le t，所以 c_u - s(out_u) > 0。又因为一个 s 序列可以唯一确定每个 u 剩余物品数量，所以完全可以把 u 剩余物品数量看成：

  1. 在 in_u 时刻剩余 s(in_u) 个。
  2. 在 out_u 时刻剩余 c_u - s(out_u) 个。

为了强制至少取了一个物品，在 out_u 时把取数下界设为 1 即可。

这样就可以 DP 了。把状态函数定义成 f_{i}(j,k) 表示考虑到 dfs 序中第 i 个位置，且 u\in P(fa_{p_i},1) 都在第二步被取了至少一个物品且 s(i-1) = k，一共取了 j 个物品的最大价值。

分情况讨论：

  1. 1. $p_i$ 不取物品。此时整个子树都不取物品，但是可以在第一步被选择。枚举有 $x$ 个在第一步被选择，记 $g_u(x)$ 表示在 $u$ 子树中前 $x$ 大价值和（点 $p$ 的价值定义为 $val_p = \sum\limits_{q\in P(p,1)}^{}v_p$）。有 $f_{out_{p_i}+1}(j,k+x)\gets f_{i}(j,k)+g_{p_i}(x)$。 2. $p_i$ 取物品。枚举取的物品数量 $x$，满足 $x \in [0,k]$。有 $f_{i+1}(j+x,k)\gets f_{i}(j,k)+x\cdot v_{p_i}$。

初始化 f_{1}(0,0) = 1。答案为 \max\limits_{j=0}^{k}f_{2n + 1}(j,t)。

对于情况 1.2 和 2 的转移，可以直接单调队列优化。对于情况 1.1，因为 g_u 是凸的，所以可以直接决策单调性优化。

时间复杂度 O(nkt\log t)。

代码

const int N = 1e4 + 10, inf = 1e18;
int n, K, t;
int c[N], v[N], val[N];
vector<int> e[N];
vector<vector<int>> f[N << 1];
vector<int> g[N];
int p[N << 1], in[N], ot[N], cnt;
int qu[N], hh, tt;

il vector<int> merge(vector<int> v1, vector<int> v2){
    vector<int> v3;
    v3.emplace_back(0);
    int x = 1, y = 1, z = 0;
    while(z < t && (x < v1.size() || y < v2.size())){
        if(x == v1.size()) v3.emplace_back(v2[y ++]);
        else if(y == v2.size()) v3.emplace_back(v1[x ++]);
        else if(v1[x] > v2[y]) v3.emplace_back(v1[x ++]);
        else v3.emplace_back(v2[y ++]);
        ++ z;
    }
    return v3;
}
il void dfs(int u){
    g[u].emplace_back(0);
    val[u] += v[u];
    if(t) g[u].emplace_back(val[u]);
    in[u] = ++cnt, p[cnt] = u;
    for(auto v: e[u]){
        val[v] = val[u], dfs(v);
        g[u] = merge(g[u], g[v]);
    }
    ot[u] = ++cnt, p[cnt] = u;
    return ;
}
il void work(int l, int r, int L, int R, int I, int J, int j){
    if(L > R || l > r) return ;
    if(l == r){
        U(k, max(l, L), R) f[J][j][k] = max(f[J][j][k], f[I][j][k - l] + g[p[I]][l]);
        return ;
    }
    int mid = L + R >> 1, mx = -inf, id = l;
    U(i, l, min(mid, r)){
        int V = f[I][j][mid - i] + g[p[I]][i];
        if(V >= mx) mx = V, id = i;
    }
    f[J][j][mid] = max(f[J][j][mid], mx);
    work(l, id, L, mid - 1, I, J, j);
    work(id, r, mid + 1, R, I, J, j);
    return ;
}

il void solve(){ 
    n = rd, K = rd, t = rd;
    U(i, 1, n) c[i] = rd, v[i] = rd;
    U(i, 2, n) e[rd].emplace_back(i);
    {
        dfs(1);
        U(i, 0, cnt + 1){
            f[i].resize(K + 2);
            U(j, 0, K){
                f[i][j].resize(t + 2);
                U(k, 0, t) f[i][j][k] = -inf;
            }
        }
        U(u, 1, n){
            vector<int> fuc; fuc.swap(g[u]);
            int sum = 0;
            U(i, 0, fuc.size() - 1){
                sum += fuc[i];
                g[u].emplace_back(sum);
            }
        }
        f[1][0][0] = 0;
    }
    U(i, 1, cnt){
        int u = p[i];
        if(in[u] == i){
            U(j, 0, K) work(0, g[u].size() - 1, 0, t, i, ot[u] + 1, j);
            U(k, 0, t){
                hh = 1, tt = 0;
                U(j, 0, K){
                    while(hh <= tt && (f[i][qu[tt]][k] - qu[tt] * v[u]) < (f[i][j][k] - j * v[u])) --tt;
                    qu[++ tt] = j;
                    while(hh <= tt && qu[hh] < max(0ll, j - k)) ++hh;
                    if(hh <= tt) f[i + 1][j][k] = max(f[i + 1][j][k], f[i][qu[hh]][k] - qu[hh] * v[u] + j * v[u]);
                }
            }
        }
        else{
            U(dk, 0, 1){
                U(k, 0, t - dk){
                    hh = 1, tt = 0;
                    U(j, 0, K){
                        while(hh <= tt && qu[hh] < max(0ll, j - (c[u] - (k + dk)))) ++hh;
                        if(hh <= tt) f[i + 1][j][k + dk] = max(f[i + 1][j][k + dk], f[i][qu[hh]][k] - qu[hh] * v[u] + j * v[u] + dk * val[u]);
                        while(hh <= tt && (f[i][qu[tt]][k] - qu[tt] * v[u]) < (f[i][j][k] - j * v[u])) --tt;
                        qu[++ tt] = j;
                    }
                }
            }
        }
    }
    int res = 0;
    U(j, 0, K) res = max(res, f[cnt + 1][j][t]);
    cout << res << "\n";
    return ;
}