题解：P3780 [SDOI2017] 苹果树

· · 题解

Sol

关键在于转化题意，题意等价于选定根为一端的一条路径，不计代价地选择路径上每个点各一个苹果，然后在剩下的苹果中满足依赖性质地选择至多 k 个，求最大价值。

然后不难想到这条路径在叶子结尾显然不劣。于是我们可以把树分为三部分：路径左侧的点，路径右侧的点，以及路径上的点。先序后序各遍历一遍做树上依赖性背包即可，可以将路径上的点与路径左侧的点合并，然后路径上的个数视作 a_i-1 跑，离开节点更新父亲答案时再强制加上一个这个节点的价值以满足依赖性。

DP 时不考虑免费节点的价值，最后统计答案时再处理路径的权值信息会方便很多。多重背包需要单调队列优化。由于我们只关心叶子节点的答案，所以所有更新部分都要在父节点处进行。

卡空间差评。一个神秘的优化是清空 vector 时使用 vector<int>().swap(f[i]) 替代 f[i].clear()，不知道为什么十分有效。

Code

const int N=2e4+1,K=5e5+1;

int n,k;
int fa[N],a[N],v[N];
vec<int> f[N],h[N];int s[N];
vec<int> g[N];
int ans;

pii q[K];int hd,tl;

void dfs(int x){
    s[x]=s[fa[x]]+v[x];
    hd=1,tl=0;
    rep(i,0,k){
        int vl=f[fa[x]][i]-i*v[x];
        while(hd<=tl&&q[tl].sec<=vl)--tl;
        q[++tl]={i,vl};
        while(hd<=tl&&i-q[hd].fir>a[x]-1)++hd;
        f[x][i]=q[hd].sec+i*v[x];
    }
    for(auto y:g[x]){
        dfs(y);
        rep(i,1,k)chmax(f[x][i],f[y][i-1]+v[y]);
    }
}
void dfs1(int x){
    reverse(g[x].begin(),g[x].end());
    for(auto y:g[x]){
        rep(i,0,k)h[y][i]=h[x][i];
        dfs1(y);
        hd=1,tl=0;
        repl(i,0,k){
            int vl=h[y][i]-i*v[y];
            while(hd<=tl&&q[tl].sec<=vl)--tl;
            q[++tl]={i,vl};
            while(hd<=tl&&i-q[hd].fir>a[y]-1)++hd;
            chmax(h[x][i+1],q[hd].sec+i*v[y]+v[y]);
        }
    }
}

inline void Main(){
    cin>>n>>k;
    rep(i,0,n)f[i].resize(k+1),h[i].resize(k+1),g[i].clear();
    rep(i,1,n)cin>>fa[i]>>a[i]>>v[i],g[fa[i]].pub(i);
    rep(i,0,k)f[1][i]=h[1][i]=0;
    dfs(1);dfs1(1);
    ans=0;
    rep(i,1,n)if(g[i].empty())rep(j,0,k)chmax(ans,f[i][j]+h[i][k-j]+s[i]);
    put(ans);
    rep(i,1,n)
        vec<int>().swap(f[i]),
        vec<int>().swap(g[i]);
}