【题解】BZOJ3252 攻略（max 卷积）

· · 个人记录

今天学了点有关这个的有趣的东西，做一道题练练手。显然这题有好多简单的贪心方法。

给定 n 个节点的带点权的树（点权为正），选出 k 条根到叶子的路径使得路径并的权值和最大。

容易想到 dp，f_{u,i} 表示 u 子树中选择 j 条路径的最大路径并权值和。我们有类似背包的转移。

f_{u,i}=\max_{0\le k\le i} f_{u,i-k}+f_{v,k}

最后 f_{u,i}:=f_{u,i}+[i>0]w_u。

我们发现这是一个类似卷积的东西，称此为 max 卷积。一个重要的性质是，两个上凸函数做 max 卷积，最终得到的还是上凸函数（下凸的做 min 卷积也是同理的）。同时我们称此为两个凸壳的闵科夫斯基和。

我们把转移写的奇怪一点：

f_{u,i}=[i>0]w_u+\max_{\sum c_v=i} \sum_{v} f_{v,c_v}

我们发现 f_{u} 即所有 f_{v} 的 max 卷积，然后最后 i>0 的位置加上 w_u。

怎么求闵科夫斯基和呢？考虑维护斜率（这里即差分），对于每个 u 记录差分数组（让我们忽略掉 i=0 吧，它没有任何价值）。对于这两个凸壳做 max 卷积，相当于对其差分做归并排序。很简单，我们用可并堆即可维护。【然后顺便复习了下几百年前写的可并堆】。

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define per(i,a,b) for(register int i=(a);i>=(b);i--)
using namespace std;
const int N=2e5+9; 

inline long long read() {
    register long long x=0, f=1; register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48,c=getchar();}
    return x*f;
}

int n,k,a[N];
vector<int>e[N];

int ls[N],rs[N],val[N],d[N],rt[N],id[N];
int merge(int x,int y) {
    if(x==0||y==0) return x+y;
    if(val[y]>val[x]) swap(x,y);
    rs[x]=merge(rs[x],y);
    if(d[ls[x]]<d[rs[x]]) swap(ls[x],rs[x]);
    d[x]=d[rs[x]]+1;
    return x;
}
int find(int x) {return rt[x]==x?x:rt[x]=find(rt[x]);}
void del(int x) {
    rt[x]=rt[ls[x]]=rt[rs[x]]=merge(ls[x],rs[x]);
    rs[x]=ls[x]=d[x]=0;
}

void dfs(int u,int fa) {
    for(auto v:e[u]) if(v!=fa) {
        dfs(v,u);
        if(!id[u]) id[u]=id[v];
        else id[u]=merge(id[u],id[v]);
    }
    if(!id[u]) {
        id[u]=u, rt[u]=u, val[u]=a[u];
    } else {
        val[id[u]]+=a[u];
    }
}

signed main() {
    n=read(), k=read();
    rep(i,1,n) a[i]=read();
    rep(i,2,n) {
        int u=read(), v=read();
        e[u].push_back(v), e[v].push_back(u);
    }
    dfs(1,0);
    int ans=0, now=rt[id[1]];
    while(now&&k) {
        k--;
        ans+=val[now];
        del(now);
        now=rt[now];
    }
    printf("%lld\n",ans);
    return 0;
}