BZOJ5252 八省联考2018林克卡特树（动态规划+wqs二分）

　　假设已经linkcut完了树，答案显然是树的直径。那么考虑这条直径在原树中是怎样的。容易想到其是由原树中恰好k+1条点不相交的链（包括单个点）拼接而成的。因为这样的链显然可以通过linkcut拼接起来，而若选择不超过k条链则可能有链不得不被cut拆开，即使不会被拆开也可以通过选择单点来达到恰好k+1条（下设k=k+1）。

　　那么问题变为在树上选择k条点不相交的链使边权和最大。最简单的dp就是设f[i][j]为i子树中选j条链的最大权值，且用一维012状态记录i这个点在子树中的度数，转移类似于一个树形背包。复杂度看起来是O(nk^2)，实际上似乎是O(nk)，可以拿60分。

　　然而再往上即使复杂度去一个k也没有更高的分了。这暗示我们可以做到与k无关的复杂度。

　　考虑去掉k的限制。这样仍然是一个dp，只是去掉了一维，复杂度变为O(n)。注意一些细节，比如说仅选择单点看做度数为1，按照210的顺序更新等等。

　　k怎么办？考虑wqs二分，也叫凸优化、带权二分啥的。我们把选择x条链的代价设为x*cost。可以发现，如果把cost设成-inf，那么会选择n条链；如果设成inf，会选择0条链；而随着cost从-inf增加到inf，最优链数感觉上应该是单调不增的。那么我们可以二分cost，使得链数最终在k处停止，这个时候肯定求得了选k条链的最优方案，于是再补回cost就可以求得最优解了。至于这个东西是不是单调不增的呢？貌似是的。为什么呢？大胆猜想不用证明感觉一个东西便宜的时候都不买，涨价了更没有理由买啊。证明我也不懂。

　　dp的时候记录一下最优的时候至少需要选择几条链。因为cost可能与一段链数对应，有可能无法刚好二分到选了k条链，不过这说明他们在该情况下都能作为最优解，则他们的加权（x*cost）答案相同。那么只要能够二分到这种加权答案就可以算出来k条链的答案了。于是保留选择的链数最接近k而又不超过k的答案，最终答案加上k*cost。

　　还有一个细节，cost只需要在整数范围内二分就可以了。具体还是用坐标系来理解吧，链数对应的实际答案构成一个凸壳，用斜率为cost的直线去切这个凸壳，第一个碰上的点就是我们找到的答案。因为其中都是整点，用整数的斜率去切就可以了。但其实我也不知道我在说啥。

　　“题目并不难。”

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 300010

#define ll long long

#define inf 300000000010

#define max(a,b) (((a)>(b))?(a):(b))

int n,k,p[N],t=;

ll ans;

struct data2

{

    ll x;int cnt;

    bool operator >(const data2&a) const

    {

        return x>a.x||x==a.x&&cnt<a.cnt;

    }

    data2 operator +(const data2&a) const

    {

        return (data2){x+a.x,cnt+a.cnt};

    }

    data2 operator -(const data2&a) const

    {

        return (data2){x-a.x,cnt-a.cnt};

    }

}f[N][];

struct data{int to,nxt,len;

}edge[N<<];

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

void dfs(int k,int from,ll cost)

{

    f[k][]=(data2){,};f[k][]=(data2){-cost,};f[k][]=(data2){-inf,};

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=from)

    {

        int y=edge[i].to;

        dfs(y,k,cost);

        data2 w=max(f[y][],max(f[y][],f[y][]));

        data2 u=f[y][]+(data2){edge[i].len+cost,-},v=f[y][]+(data2){edge[i].len,};

        f[k][]=max(f[k][]+w,f[k][]+max(u,v));

        u=f[y][]+(data2){edge[i].len,},v=f[y][]+(data2){edge[i].len-cost,};

        f[k][]=max(f[k][]+w,f[k][]+max(u,v));

        f[k][]=f[k][]+w;

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5252.in","r",stdin);

    freopen("bzoj5252.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read(),k=read()+;

    for (int i=;i<n;i++)

    {

        int x=read(),y=read(),z=read();

        addedge(x,y,z),addedge(y,x,z);

    }

    ll l=-inf,r=inf;

    while (l<=r)

    {

        ll mid=l+r>>;

        dfs(,,mid);

        if (max(f[][],max(f[][],f[][])).cnt<=k) ans=max(f[][],max(f[][],f[][])).x+k*mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

    return ;

}

巴特西

BZOJ5252 八省联考2018林克卡特树（动态规划+wqs二分）

最新文章

热门文章