专栏文章

题解：P12444 [COTS 2025] 发好奖 / Hijerarhija

KKaf_yoU
P12444题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@min1lcqu
此快照首次捕获于
2025/12/01 19:04
3 个月前
此快照最后确认于
2025/12/01 19:04
3 个月前
查看原文
清新 trick，记在小本本上了。
题意简述：
nn 个点，每个点可以选或不选；选第 ii 个点的代价为 cic_i，贡献为 pip_i；若选择了点 ii 则其父节点的代价必须至少为 11（不一定要选，即不一定要达到 cic_i）。
求代价不超过 kk 的情况下能获得的最大贡献之和。
考虑每个点的代价，每个点要么不选要么选，若其所有子节点内有节点选了但该点不选则设其代价为 11（更多显然不优）。
相当于在普通树形背包 00 或 cic_i 的代价外额外多了一种 11 的代价。发现这个东西直接从子树转移的时候需要枚举子树状态，有 O(nk2)\mathcal{O}(nk^2) 的暴力 DP，但是显然是错误的。
正着优化十分困难！所以抛开之前所有思路，有一个妙妙 trick。
精简对于有 / 无代价的定义，如果一个点 ii 的代价为正整数（11 或 cic_i），则其子树内的所有点都可以花费任意代价，否则只能为 00。
这个表述看上去仅和子树相关，联想一个性质：子树内部的 DFS 序连续。
trick 即为在 DFS 序上 DP。具体的，设 fi,jf_{i,j} 为 DFS 序意义下前 ii 个人，代价为 jj 的最大贡献。
对代价的三种取值分别考虑转移：
  • 点 ii 被计算的代价为 00；意味着 ii 的子树内不能有大于 00 的代价花费，只能令其去更新子树外的答案：
    fi+sizi,j←max⁡(fi+sizi,j,fi,j)f_{{\color{red}i}+\text{siz}_i,j}\gets\max(f_{{\color{red}i}+\text{siz}_i,j},f_{{\color{red}i},j})
    其中 sizi\text{siz}_i 表示 ii 的子树大小。
  • 点 ii 被计算的代价为 11；此时可以有子树内的点被选，仅 ii 本身不算；直接更新下一个点：
    fi+1,j+1←max⁡(fi+1,j+1,fi,j)f_{{\color{red}i}+1,j+1}\gets\max(f_{{\color{red}i}+1,j+1},f_{{\color{red}i},j})
  • 点 ii 被计算的代价为 cic_i；子树内的点依然可以选，同时 ii 本身也计入贡献。更新的对象与上一种相同:
    fi+1,j+ci←max⁡(fi+1,j+ci,fi,j+pi)f_{{\color{red}i}+1,j+c_i}\gets\max(f_{{\color{red}i}+1,j+c_i},f_{{\color{red}i},j}+p_i)
需要注意的是，为方便表述，上述文字中的 ii 和转移式中的 ii 意义并不完全一样，由于是按 DFS 序 DP，所以转移式中单独的 ii 表示的是点 ii 的 DFS 序（用红色标出）。
答案取 max⁡fn+1,i∈[0,m]\max f_{n+1,i\in[0,m]}。之所以 n+1n+1 是由于该 DP 为扩散型。
C
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int N = 5e3 + 10, kafu = -2021070767;
int n, k, dfn[N], d2i[N], siz[N], f[N][N], c[N], p[N], dcnt;
vector <int> g[N];
int cmax (int &x, int y) { return x = max (x, y); }

void DFS (int u)
{
    dfn[u] = ++ dcnt, siz[u] = 1;
    for (int v : g[u]) DFS (v), siz[u] += siz[v];
}

int main ()
{
    cin >> n >> k;
    for (int i = 2, fa; i <= n; i ++)
        cin >> fa, g[fa].push_back (i);
    DFS (1);
    for (int i = 1; i <= n; i ++) d2i[dfn[i]] = i;
    for (int i = 1; i <= n; i ++) cin >> p[i];
    for (int i = 1; i <= n; i ++) cin >> c[i];
    
    for (int i = 1; i <= n; i ++) fill (f[i], f[i] + 1 + k, kafu);
    f[1][0] = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 0; j <= k; j ++)
        {
            if (f[i][j] == kafu) continue;
            int ti = d2i[i];
            cmax (f[i + siz[ti]][j], f[i][j]);
            cmax (f[i + 1][j + 1], f[i][j]);
            if (j + c[ti] <= k)
                cmax (f[i + 1][j + c[ti]], f[i][j] + p[ti]);
        }
    // for (int i = 1; i <= n; i ++, cout << '\n')
    //     for (int j = 0; j <= k; j ++) cout << f[i][j] << ' ';
    int ans = 0;
    for (int i = 0; i <= k; i ++)
        if (f[n + 1][i] != kafu) ans = max (ans, f[n + 1][i]);
    cout << ans;
    return 0;
}
使用 DFS 序 DP 的方便之处在于首种转移，用于方便的排除子树影响，严肃记忆.jpg。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...