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

MoYuFang · 2021-11-08 22:26:40 · 题解

P4383 [八省联考2018]林克卡特树

首先可以将题意化简为在树上选 k+1 个没有公共点的树链，求树链边权和最大。

写出树上背包，设 f(u, x, 0/1/2) 表示当前子树的根为 u，子树内有 x 个不相交的链，且根 u 状态为 0/1/2 时的最大边权和，0 代表 u 自己一个点占一条链，1 代表 u 接在某一儿子的链上，2 代表 u 不在链上或接在某对儿子的链上。

这个树上背包的复杂度是 O(nk)，能拿到 60pts。

然后不会了。

题解说是 \text{wqs} 二分。

这个问题抽象一下就是限定物品数量的背包问题，即给定物品数量 k，求恰好选 k 个物品的最大权值。

直接用背包 \text{dp} 复杂度怎么也不能低于 O(nk)。

不妨设 h(x) 表示恰好选 x 物品时的的答案，若 h(x) 是凸函数，即 h^{\prime}(x) 单调（离散函数的导数可以理解成差分），则可以用 \text{wqs} 二分将时间复杂度优化至 n\log w，其中 w 为 h^{\prime}(x) 的绝对值的最大值。

为了方便，代码实现中可以将 f 与 g 封装进一个二元组，然后定义二元组的比较函数。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <iostream>
#include <assert.h>
using namespace std;

#define re register
#define sf scanf
#define pf printf
#define nl() putchar('\n')
#define ms(x, val) memset(x, val, sizeof(x))
#define ll long long
#define _for(i, a, b) for(re int (i) = (a); (i) < (b); ++(i))
#define _rfor(i, a, b) for(re int (i) = (a); (i) <= (b); ++(i))
#define _fev(p, u) for(re int (p) = head[(u)]; (p); (p) = nex[(p)])
#define inf 0x7ffffffffffffffll
#define ninf (-inf)
#define maxn 300005
#define maxk 105

template <class T>
void print(string name, T arr[], int n, int flag = 1){
    cout<<name<<":";
    _for(i, 0, n)cout<<" "<<arr[i+flag];
    cout<<endl;
}

int rdnt(){
    re int x = 0, sign = 1;
    re char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (c ^ 48), c = getchar();
    return x * sign;
}

int ecnt = 1, k,
    head[maxn],
    to[maxn*2],
    nex[maxn*2],
    we[maxn*2];
ll  mi;
struct Par{
    ll f; int g;
    inline bool operator<(const Par &t)const{ return (f == t.f) ? (g < t.g) : (f < t.f); }
} par[maxn][3];
#define f(u, fg) par[u][fg].f
#define g(u, fg) par[u][fg].g

void add_edge(re int u, re int v, re int w){
    to[++ecnt] = v; nex[ecnt] = head[u]; head[u] = ecnt; we[ecnt] = w;
    to[++ecnt] = u; nex[ecnt] = head[v]; head[v] = ecnt; we[ecnt] = w;
}

#define sum(x, y, z) ((x == ninf || y == ninf) ? (ninf) : (x+y+z))
void ud(Par &x, Par y){ if (x < y) x = y; }

void dfs(int u, int fa){
    f(u, 0) = -mi; f(u, 2) = 0; f(u, 1) = ninf;
    g(u, 0) = 1; g(u, 2) = 0; g(u, 1) = 0;
    _fev(p, u){
        int v = to[p];
        if (v == fa) continue;
        dfs(v, u);
        Par tu1, tu2, tv1 = max(par[v][0], par[v][1]), tv2 = max(tv1, par[v][2]);

        tu1.f = sum(f(u, 1), tv1.f, we[p] + mi); tu1.g = g(u, 1) + tv1.g - 1;
        tu2.f = sum(f(u, 2), tv2.f, 0); tu2.g = g(u, 2) + tv2.g;
        ud(par[u][2], max(tu1, tu2));

        tu1.f = sum(f(u, 0), tv1.f, we[p] + mi); tu1.g = g(u, 0) + tv1.g - 1;
        tu2.f = sum(f(u, 1), tv2.f, 0); tu2.g = g(u, 1) + tv2.g;
        ud(par[u][1], max(tu1, tu2));

        tu1.f = sum(f(u, 0), tv2.f, 0); tu1.g = g(u, 0) + tv2.g;
        ud(par[u][0], tu1);

    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    #endif

    re int n = rdnt(); k = rdnt()+1;
    re ll l, r = 0, as = ninf;
    _rfor(i, 1, n-1){
        re int u = rdnt(), v = rdnt(), w = rdnt();
        if (w > 0) r += w; 
        add_edge(u, v, w);
    }
    l = -r; ++r;
    while(l < r){
        mi = (l+r)>>1;
        dfs(1, 0);
        Par ans = max(par[1][0], par[1][1]);
        ans = max(ans, par[1][2]);
        //pf("mi:%lld af:%lld ag:%d\n", mi, ans.f + ans.g*mi, ans.g);
        if (ans.g >= k) as = ans.f + ans.g*mi, l = mi+1;
        else r = mi;

    }
    pf("%lld\n", as);


    return 0;
}