「BZOJ5252」林克卡特树

给定一棵点数为 $n$的树,树上的每个边有一个整数边权,要求选择恰好 $k$ 条没有交集的路径,使得路径上的边的边权和最大。

学习了一下 wqs 二分,感觉非常厉害。

wqs 二分的常见套路是,对于一些 DP 状态在两维以上的题目,满足某些性质的前提下,可以把一维的状态通过二分降为$\log $ 的复杂度,同时可以嵌套,即如果多维状态都满足,那么这些状态都能降为 $\log$。

一般的类型是要求在某个范围内选择恰好 $k$ 个满足某些特殊要求的数据,不妨称之为 $k$ 个决策,使得其和最大或者最小。不妨假设 DP 的状态为 $f(i,j)$,其中 $j$ 是我们要求满足的决策数,我们令 $g(j)$表示在第二维的状态为 $j$ 时,DP 可以得到的最优解。我们将$(x, g(x))$ 画在二维平面上,如果其可以构成一个上凸壳或者下凸壳,就满足 wqs 二分优化的条件,也叫 DP 凸优化。

这个时候,因为其是一个凸壳,所以斜率满足单调性,我们可以尝试二分斜率,但是怎么通过二分的值来影响 DP 的过程呢,我们发现我们画在二维平面上的凸壳是以决策数为 $x$ 的,同时只有每次 DP 的转移才会影响到决策数,那么我们可以考虑每次转移时,对于每个决策新增一个额外的代价,即我们二分得到的斜率,具体是加还是减取决于凸壳的形式,这个时候我们取 DP 的出来的最优值,同时计算出来得到这个最优值所需要的决策数,就能完成二分的判定了。

考虑这个题目,很容易想到 $nk$ 的 DP,结合上面所说的优化即可。

具体细节参考代码,时间复杂度 $O(n\log W)$。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<ll, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while (ch > '9' || ch < '0') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

const int MAXN = 3e5 + 5;
const ll oo = 1e18;

int fix;

inline pr operator + (const pr & a, const pr & b) { return make_pair(a.fi + b.fi, a.se + b.se); }

inline pr upd(pr w, int v, int o){
    w.fi += v; w.fi -= o * fix;
    w.se += -o;
    return w;
}

pr f[MAXN][3];

int N, K;

struct edge {
    int y, next, v;
}e[MAXN << 1];

int LINK[MAXN], len = 0;

inline void ins(int x, int y, int v){
    e[++len].next = LINK[x]; LINK[x] = len;
    e[len].y = y; e[len].v = v;
}

inline void Ins(int x, int y, int v){
    ins(x, y, v);
    ins(y, x, v);
}

void DFS(int node, int fa){
    f[node][0] = make_pair(0LL, 0);
    f[node][1] = make_pair(-fix, -1);
    f[node][2] = make_pair(-oo, 0);
    pr g[3];
    Auto (i, node) if (e[i].y != fa) {
        DFS(e[i].y, node);
        up (j, 0, 2) g[j] = f[node][j], f[node][j] = make_pair(-oo, 0);
        up (j, 0, 2) up (k, 0, 2) if (f[e[i].y][k].fi != -oo)
            cmax(f[node][j], g[j] + f[e[i].y][k]);
        if (f[e[i].y][1].fi != -oo) cmax(f[node][1], g[0] + upd(f[e[i].y][1], e[i].v, 0));
        if (f[e[i].y][0].fi != -oo) cmax(f[node][1], g[0] + upd(f[e[i].y][0], e[i].v, 1));
        if (f[e[i].y][1].fi != -oo) cmax(f[node][2], g[1] + upd(f[e[i].y][1], e[i].v, -1));
        if (f[e[i].y][0].fi != -oo) cmax(f[node][2], g[1] + upd(f[e[i].y][0], e[i].v, 0));
    }
}

pr calc(int k){
    fix = k;
    DFS(1, 0);
    pr w = make_pair(-oo, 0);
    up (i, 1, N) up (j, 0, 2) cmax(w, f[i][j]);
//    printf("%lld %lld %d\n", k, w.fi, w.se);
    return w;
}

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
#endif
    N = read(); K = read() + 1;
    up (i, 2, N) {
        int x = read(), y = read(), v = read();
        Ins(x, y, v);
    }
    int le = -1e8, ri = 1e8, mi;
    while (le + 1 < ri) {
        mi = (le + ri) / 2;
        if (-calc(mi).se <= K) ri = mi;
        else le = mi;
    }
    ll ans = -oo;
    up (i, le, ri) {
        pr w = calc(i);
        if (-w.se <= K) cmax(ans, w.fi + (ll)K * i);
    }
    printf("%lld\n", ans);
    return 0;
}