顺流而下 / River Rafting JOI 2026 SemiFinal

WZH2026-10-162026-10-16

[JOI 2026 SemiFinal] 顺流而下 / River Rafting

[JOI 2026 SemiFinal] 顺流而下 / River Rafting。

JOI 国有 $N$ 个城镇，城镇编号为 $1$ 到 $N$ 。这些城镇之间有 $N-1$ 条道路，编号为 $1$ 到 $N-1$ 。道路 $i$ ( $1 \le i \le N-1$ ) 双向连接城镇 $P_i$ ( $P_i \le i$ ) 和城镇 $i+1$ 。保证从城镇 $1$ 出发，可以通过若干条道路到达任意城镇。

此外，JOI 国有 $N-1$ 条与道路平行的河流，河流编号为 $1$ 到 $N-1$ 。河流 $i$ ( $1 \le i \le N-1$ ) 与道路 $i$ 平行，从城镇 $P_i$ 流向城镇 $i+1$ 。

$N$ 个城镇中各放置了一盏灯。每盏灯都有一个强度。当城镇 $t$ ( $1 \le t \le N$ ) 处的灯强度为 $l$ 时，从该城镇出发，经过少于 $l$ 条道路可以到达的城镇都会被这盏灯照亮。初始时，所有灯的强度均为 $0$ ，没有任何城镇被照亮。

你可以进行任意次（包括 $0$ 次）顺流而下。每次顺流而下从位于城镇 $1$ 的状态开始，首先将城镇 $1$ 处的灯强度增加 $1$ 。然后，依次重复以下操作：

决定是否结束本次顺流而下。但如果当前所在城镇没有流出的河流，则必须结束。

若继续顺流而下，则从当前城镇流出的河流中选择一条，沿着该河流移动。移动后，将到达的城镇处的灯强度增加 $1$ 。

若在城镇 $t$ 结束本次顺流而下，则此次顺流而下产生的成本为 $C_t$ 。你希望通过进行若干次顺流而下，使得每个城镇都至少被一盏灯照亮。在此基础上，需要最小化顺流而下产生的总成本。

$n\le 700,C_i\le 10^9,P_i\le i$ 。

首先看起来一个点的灯照亮的是邻域，但是由于任意一个点的父亲必然比自己亮，所以实际上一个点的作用仅限于自己子树内。

然后考虑设状态： $f_{i,j}$ 表示 $i$ 子树内满足 $i$ 有 $j$ 盏灯时都填满的最小代价。然而这样有一个限制：可能有些儿子的子树完全不选，由 $i$ 自己照亮；或者说 $i$ 照亮一部分，剩下的部分儿子自给自足。

因此我们的状态要加一维 $k$ ： $f_{i,j,k}$ 表示 $i$ 子树内， $j$ 盏灯，距离 $i$ 最远的没有被照射的点距离 $i$ 为 $k-1$ ；特别的， $k=0$ 意味着没有点没有被照射。

那么我们可以写出转移：

f_{x,i+j,\max\{p,q+1\}}\leftarrow f_{x,i,p}+f_{u,j,q}

特别的，对于 $0$ ，我们有转移：

f_{x,i,0}\leftarrow f_{u,j,i}+\max\{i-j,0\}mn_i

其中 $mn_i$ 表示 $i$ 子树内最小的 $C$ 的值。

这样你就成功获得 $56\%$ 的分数，复杂度 $\mathcal{O}(n^4)$ 。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=710;
const ll inf=1e15;
int n,mn[N],sz[N],a[N];
vector<int>v[N];
void dfs(int x){
    mn[x]=a[x];
    for(int u:v[x]){
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
#define upd(a,b) a=min(a,b)
vector<vector<ll>> dfs2(int x){
    sz[x]=1;
    vector<vector<ll>>f(2,vector<ll>(2,inf));
    f[0][1]=0;
    for(int u:v[x]){
        vector<vector<ll>>h=dfs2(u);
        vector<vector<ll>>g(sz[x]+sz[u]+1,vector<ll>(sz[x]+sz[u]+1,inf));
        for(int i=0;i<=sz[x];i++)for(int j=0;j<=sz[x];j++)
            for(int p=0;p<=sz[u];p++)for(int q=0;q<=sz[u];q++)
                upd(g[i+p][max(j,q+1)],f[i][j]+h[p][q]);
        sz[x]+=sz[u];
        f=g;
    }
    for(int i=0;i<=sz[x];i++)
        for(int j=0;j<=sz[x];j++)
            upd(f[i][0],f[j][i]+(ll)max(i-j,0)*mn[x]);
    return f;
}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<n;i++){
        scanf("%d",&x);
        v[x].push_back(i+1);
    }
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    dfs(1);
    vector<vector<ll>>f=dfs2(1);
    ll ans=inf;
    for(int i=0;i<=n;i++)ans=min(ans,f[i][0]);
    printf("%lld",ans);
    return 0;
}

::::

接着考虑优化：前面两维使用树形背包的优化可以在 $\mathcal{O}(n^2)$ 的时间内解决，主要是后面的 $\max$ 不好处理，因此我们可以这样改变状态：

定义 $f_{i,j,k}$ 表示 $i$ 子树内， $j$ 盏灯，距离 $i$ 最远的没有被照射的点距离 $i$ 少于 $k-1$ ；特别的， $k=0$ 意味着没有点没有被照射。

这样转移突然就变得简单了：

f_{x,i+j,k}\leftarrow f_{x,i,k}+f_{u,j,k-1}

原因是 $\max$ 被合并了，而 $\min-\operatorname{plus}$ 具有分配律。

然后就可以 $\mathcal{O}(n^3)$ 解决此题了。

PS: 卡空间，要 vector。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=710;
const ll inf=1e15;
int n,mn[N],sz[N],a[N];
vector<int>v[N];
void dfs(int x){
    mn[x]=a[x];
    for(int u:v[x]){
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
#define upd(a,b) a=min(a,b)
vector<vector<ll>> dfs2(int x){
    sz[x]=1;
    vector<vector<ll>>f(2,vector<ll>(2,inf));
    f[0][1]=0;
    for(int u:v[x]){
        vector<vector<ll>>h=dfs2(u);
        vector<vector<ll>>g(sz[x]+sz[u]+1,vector<ll>(sz[x]+sz[u]+1,inf));
        for(int i=0;i<=sz[x];i++)for(int j=0;j<=sz[u];j++)
            for(int p=1;p<=sz[x]+sz[u];p++)
                upd(g[i+j][p],f[i][min(p,sz[x])]+h[j][min(p-1,sz[u])]);
        sz[x]+=sz[u];
        f=g;
    }
    for(int i=0;i<=sz[x];i++)
        for(int j=0;j<=sz[x];j++)
            upd(f[i][0],f[j][i]+(ll)max(i-j,0)*mn[x]);
    for(int i=0;i<=sz[x];i++)
        for(int j=1;j<=sz[x];j++)
            upd(f[i][j],f[i][j-1]);
    return f;
}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<n;i++){
        scanf("%d",&x);
        v[x].push_back(i+1);
    }
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    dfs(1);
    vector<vector<ll>>f=dfs2(1);
    ll ans=inf;
    for(int i=0;i<=n;i++)ans=min(ans,f[i][0]);
    printf("%lld",ans);
    return 0;
}