题解 P4657 [CEOI2017]Chase

· · 题解

Solution

当我们固定一个起点后 , 把起点作为整个树的根 , 那么这时每个节点选不选的价值就是它所有儿子的铁球数量加和 .
那么设 f_{i,j} 表示在 i 子树里选择了 j 个点所能得到的最大贡献 , 转移时考虑这个节点是否选择 .
设 son_i 表示 i 节点的儿子 , v_i 表示 i 节点的所有儿子铁球数量和 .

f_{i,j}=\max(f_{son_i,j},f_{son_i,j-1}+v_i)

枚举起点作为根 , 复杂度 O(n^2v).
不能通过本题 ,
考虑沿用上面对价值的定义 , 设计新的 dp,
设 f_{i,j,0/1},g_{i,j,0/1} 分别表示从 i(i的子树)走到 i 的子树(i)中 , i 被/不被)选 , 选了 j 个的最大贡献 .
设当前节点为 u , 儿子为 son, 父亲为 fa , 当前节点儿子权值和为 v , 点 i 的铁球数量为 p_i.
那么有转移

f_{u,j,0}=\max(f_{son,j,0},f_{son,j,1}) f_{u,j,1}=\max(\max(f_{son,j-1,0},f_{son,j-1,1})+v) g_{u,j,0}=\max(g_{son,j,0},g_{son,j,1}) g_{u,j,1}=\max(\max(g_{son,j-1,0},g_{son,j-1,1})+v+p_{fa}-p_{son})

注意路径方向的不同导致的价值变化 .
还要考虑 u 自己作为起点 ,
即 g_{u,1,1}=\max(v+p_{fa})
但直接使用一个点的 f 和 g 去更新答案 , 无法保证路径不重复 ,
那么考虑在合并子树时更新答案 ,

ans=\max(\max(f_{son,j,0},f_{son,j,1})+\max(g_{u,k,0},g_{u,k,1})) ans=\max(\max(g_{son,j,0},g_{son,j,1})+\max(f_{u,k,0},f_{u,k,1}+p_{fa}-p_{son}))

注意这里 f,g 是由之前的全部儿子转移而来 , 所以能够保证路径不重复 . 注意由于 f_{u,0,1},g_{u,0,1} 不合法 , 强制赋值负无穷 .
上式的 j+k\leq v , 如果枚举 j,k 会有 O(v^2) 的复杂度 , 实际上只需维护前缀最大值就可做到 O(v) 转移 .
时间复杂度 O(nv)

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define ll long long
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
const int maxn=1e5+5;
const int maxm=105;
const ll inf=1e15;
int n,v;
ll ans;
struct graph
{
    int p[maxn];ll val[maxn];
    int head[maxn],ver[maxn<<1],nxt[maxn<<1],tot;
    void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
    void link(int x,int y){add(x,y);add(y,x);}
    ll f[maxn][maxm][2],g[maxn][maxm][2];
    void dfs(int u,int fa)
    {
        val[u]=0;
        for(int i=head[u];i;i=nxt[i])
        {
            if(ver[i]==fa)continue;
            dfs(ver[i],u);val[u]+=p[ver[i]];
        }
        f[u][0][1]=g[u][0][1]=-inf;
        g[u][1][1]=max(g[u][1][1],val[u]+p[fa]);
        for(int i=head[u];i;i=nxt[i])
        {
            if(ver[i]==fa)continue;
            ll mx1=0,mx2=0;
            for(int j=v;j>=0;j--)
            {
                mx1=max(mx1,max(g[u][v-j][0],g[u][v-j][1]));
                mx2=max(mx2,max(f[u][v-j][0],f[u][v-j][1]+p[fa]-p[ver[i]]));
                ans=max(ans,max(f[ver[i]][j][0],f[ver[i]][j][1])+mx1);
                ans=max(ans,max(g[ver[i]][j][0],g[ver[i]][j][1])+mx2);
            }
            for(int j=1;j<=v;j++)
                f[u][j][0]=max(f[u][j][0],max(f[ver[i]][j][0],f[ver[i]][j][1])),f[u][j][1]=max(f[u][j][1],max(f[ver[i]][j-1][0],f[ver[i]][j-1][1])+val[u]);
            for(int j=1;j<=v;j++)
                g[u][j][0]=max(g[u][j][0],max(g[ver[i]][j][0],g[ver[i]][j][1])),g[u][j][1]=max(g[u][j][1],max(g[ver[i]][j-1][0],g[ver[i]][j-1][1])+val[u]+p[fa]-p[ver[i]]);
        }
    }
}o;
int main()
{
    n=read();v=read();
    for(int i=1;i<=n;i++)o.p[i]=read();
    for(int i=1;i<=n-1;i++)o.link(read(),read());
    o.dfs(1,0);
    printf("%lld",ans);
    return 0;
}