ceoi「chase」 | Hexo

归档于 2019-10-07 19:58

虽然原题是磁铁,我还是说面包屑吧

图稍小

题解

$70$分$dp$,

$f_{x,i}$表示走到$x$为止用了$i$次,枚举起点进行转移

转移$f_{x,i}=max(f_{pre,i},f_{pre,i-1}+sz_{x})$,这里$sz$表示的是儿子的权值和,不包括当前点

为什么这样转移,考虑你在当前撒下面包屑那么走到任意一个儿子差值都是这些,

不考虑父亲,在当前撒下面包屑儿子节点鸽子被吸引过来,走到儿子节点旅行家遇到鸽子数量不变,小学生遇到鸽子比旅行家多的就是儿子权值和

为什么不考虑父亲,父亲的贡献被父亲的父亲考虑了,

换种方法思考,分为三部分考虑

1.当前点,这一部分学生和旅行家都走了

2.自己走的儿子,这一部分学生走了,旅行家走的时候鸽子已经被吸引走了

3.没走的儿子,这一部分是学生直接多出来的

关于自己父亲,丢给上面节点考虑就行了,

$100$分$dp$

在这里,我先推荐一篇极好的博客

上面$dp$计算冗余太多,极限就是这些分了

首先根据上面$dp$经验,放面包屑只会让权值变大,那么这样我们先贪心考虑,放完所有面包屑一定比不放完更优

发现一段路径一定是由两部分组成的,首先$up$表示从儿子走到当前节点最大贡献,$down$表示从当前点走到子树内最大贡献,

考虑初始化你不能重复考虑父亲,于是有了

    for(ll i=1;i<=v;i++)
        up[x][i]=sum[x],down[x][i]=sum[x]-val[fa[x]];

考虑两部分拼接成答案,那么答案就是

        for(ll i=1;i<v;i++) 
            ans=max(up[x][i]+down[y][v-i],ans);

考虑为什么不是$up[x][i]+down[x][v-i]$好吧,其实挺显然的,

然后考虑转移,

$up$从下往上转移所以$-val[y]$,$down$从上往下转移所以$+val[fa[x]]$

至于为什么要-,跟上面原因类似,你在上面节点计算贡献时已经计算当前点父亲了,你全丢给了父亲以上考虑

还有很多很多很多细节,我不再一一细说了,

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 500000
ll fa[A],ver[A],nxt[A],head[A],sta[A],val[A],sum[A],up[A][101],down[A][101];
ll n,ans,tot,v,top;
void add(ll x,ll y){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
void dfs(ll x){
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa[x]) continue ;
        fa[y]=x;
        dfs(y);
    }
    for(ll i=1;i<=v;i++)
        up[x][i]=sum[x],down[x][i]=sum[x]-val[fa[x]];
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa[x]) continue ;
        sta[++top]=y;
        for(ll i=1;i<v;i++) 
            ans=max(up[x][i]+down[y][v-i],ans);
        for(ll i=1;i<=v;i++)
            up[x][i]=max(up[x][i],max(up[y][i-1]+sum[x]-val[y],up[y][i])),
            down[x][i]=max(down[x][i],max(down[y][i-1]+sum[x]-val[fa[x]],down[y][i]));
    }
    ans=max(ans,max(up[x][v],down[x][v]));
    for(ll i=1;i<=v;i++)
        up[x][i]=sum[x],down[x][i]=sum[x]-val[fa[x]];
    while(top){
        ll y=sta[top--];
        for(ll i=1;i<v;i++) 
            ans=max(up[x][i]+down[y][v-i],ans);
        for(ll i=1;i<=v;i++)
            up[x][i]=max(up[x][i],max(up[y][i-1]+sum[x]-val[y],up[y][i])),
            down[x][i]=max(down[x][i],max(down[y][i-1]+sum[x]-val[fa[x]],down[y][i]));
    }
    ans=max(ans,max(up[x][v],down[x][v]));
}
int main(){
    scanf("%lld%lld",&n,&v);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&val[i]);
    for(ll i=1,a,b;i<n;i++){
        scanf("%lld%lld",&a,&b);
        add(a,b);add(b,a);
        sum[a]+=val[b];
        sum[b]+=val[a];
    }
    dfs(1);
    printf("%lld\n",ans);
}

View Code