题解 P4383 【[八省联考2018]林克卡特树lct】

· · 题解

emm感觉其他题解都没有讲的特别清楚。写一篇讲的比较详细的吧。

带权二分，又叫wqs二分/dp凸优化，用于解决一类有固定数量限制的最优化问题。

例如，给你n个物品，给定以某些方式选择能得到某些收益/付出某些代价，问选择恰好k个物品所能得到的最大收益/付出的最小费用。

因为有了k的限制，一般来说只能够类似于f[i][j]表示前i个物品中选择了j个时的最优解这样的类似背包的方法来求解。而且这个dp看起来很难优化，因为状态数几乎是满的，而即使能够O(1)转移，最多也只能做到2D/0D，复杂度为O(nk)

但是，带权二分能够成为这类问题的一个突破口。令f(x)表示选择恰好x件物品的最优解，如果f(x)是一个凸函数，我们就能使用带权二分来优化它。

具体而言，对于x\in[0, n]，对应的f(x)在以x为横坐标，f(x)为纵坐标的二维平面内构成了一个凸包。

一个凸包的示例

我们要求的是f(k)，也就是凸包上的一个点P(k, f(k))。这个凸包不能直接下手去求，因为时间复杂度无法承受。

考虑引一条固定斜率的直线去切这个凸包，也就是从上向下平移找到最早相交的那个点，这个切点的坐标是可以求出来的(将在后文详细叙述)。也就是说我们能够确定凸包上的一个点Q(x, f(x))，并且，我们还能确定这个点在所求P点的左侧还是右侧。

引一条直线切凸包

如果Q在P的左侧，我们减小直线斜率继续尝试，否则增大直线斜率，直到正好切到P点。因为是一个凸函数，增大直线斜率后所得切点一定在Q左侧，反之亦然。

这样，我们可以通过二分直线斜率的方式来求得P点坐标，也求出对应的f(k)

黄绿红三条直线斜率依次减小，所得切点横坐标依次增大

到了现在，我们唯一需要解决的问题就是怎么找到切点坐标。

设该直线斜率为m，解析式为y=mx+b,显然要找到最高的切点就需要最大化直线的截距，也就是b。

在图像上，我们可以将凸包上的每个点(x, f(x))都向下平移至(x, f(x)-mx)，不难发现此时这仍是个凸包。此时凸包的最高点即是向下平移后的切点，证明如下：

设切点坐标为x

\because f(x)=mx+b \therefore f(x)-mx=b \therefore \max(b)=\max(f(x)-mx)

在切到了P点之后，按照上面的方式找到的其实是平移后的P点，将它向上平移还原即可。

对应到给定的题目中，只需要把每个物品的收益减去二分的斜率m，这样就能保证每多选取一个物品都需付出m的代价，然后不考虑k的限制求得最大收益w，并且求得在得到最大收益的情况下选取的物品个数c，则我们求得上述的Q(c, w+cm)，根据c和限制k的大小关系调整直线斜率继续二分即可。

回到本题，显然题目可以转化为选取k+1条路径的长度和的最大值。设f(x)为选取x条路径所得到的最优方案。出题人告诉我们这个f(x)是凸的，使用上述的二分方法，二分斜率m,令每选取一条路径都需要付出m的代价(m可能为负数)，求此时选任意条路径所能得到的最大收益以及得到最大收益的前提下选取的最大路径条数，并按照上面的方法调整斜率即可。

稍有不同的是，我们这里需要找到的是最小的可以使得选取的路径条数\geq k的斜率m，这也是为何需要选取尽量多的路径。

至于如何求出选取k+1条路径的长度和的最大值，可以使用树形dp在O(n)的时间里解决。 f[i][j] (j\in \{0, 1, 2\}) 表示点i的度数为j时i的子树中的最优解，使用背包转移即可。在具体实现中，背包这一维可以滚掉。

另外还有一些边界和细节问题，这里就不在赘述了，可以参考其他题解或者理解后自行推导。

#include <bits/stdc++.h>
#define maxn 300005
#define ll long long
const int inf=1e13;

struct edge {
    int v, w, next;
}edges[maxn<<1];

int n, k, tail=0, u, v, w, cnt, head[maxn]={0};
ll sum,delta,l,r=0,ans;

void add_edge(int u, int v, int w) {
    edges[++tail].v=v;
    edges[tail].w=w;
    edges[tail].next=head[u];
    head[u]=tail;
}

struct data{
    int c; ll v;
    data operator + (data d) {data a;a.v=v+d.v;a.c=c+d.c;return a;}
    bool operator < (data d) {return v<d.v||(v==d.v&&c<d.c);}
}dp[maxn][3], temp[3];

data dat(ll v, int c) {data d;d.v=v;d.c=c;return d;}

data max(data a, data b) {
    if (a<b) return b;
    return a;
}
void dfs(int u, int f) {
    for (int i=head[u];i;i=edges[i].next) {
        int v=edges[i].v;
        if (v==f) continue;
        dfs(v, u);
        dp[u][2]=max(dp[u][2]+dp[v][0], dp[u][1]+dp[v][1]+dat(edges[i].w-delta, 1));
        dp[u][1]=max(dp[u][0]+dp[v][1]+dat(edges[i].w, 0), dp[u][1]+dp[v][0]);
        dp[u][0]=dp[u][0]+dp[v][0];
    }dp[u][0]=max(dp[u][0], max(dp[u][1]+dat(-delta, 1), dp[u][2]));
}   

void check(ll x) {
    delta=x;
    for (int i=1;i<=n;++i) {
        dp[i][0]=dat(0, 0);dp[i][2]=dat(-delta, 1); dp[i][1]=dat(0, 0);
    } dfs(1, 0);
    sum=dp[1][0].v; cnt=dp[1][0].c;
}

int main() {
    scanf("%d %d", &n, &k);k++;
    for (int i=1;i<n;++i) {
        scanf("%d %d %d",&u,&v,&w);
        add_edge(u,v,w);add_edge(v,u,w);
        r+=(w>0)?w:-w;
    } l=-r;
    while (l<=r) {
        ll mid=(l+r)>>1;
        check(mid);
        if (cnt>=k) {l=mid+1; ans=mid;}
        else r=mid-1;
    }check(ans);
    printf("%lld", sum+k*ans);
    return 0;
}

wqs的论文:http://www.doc88.com/p-949564862405.html

最后，关于本题f(x)为什么是凸的，我翻看了很多篇博客，暂时未发现任何关于它的证明。如果有会证的dalao还烦请赐教。