洛谷P4383 [八省联考 2018] 林克卡特树题解

题目链接：P4383 [八省联考 2018] 林克卡特树

题意：

小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 LCT 的挑战，它的规则是这样子的：现在有一个 \(N\) 个点的树，每条边有一个整数边权 \(v_i\)，若 \(v_i \geq 0\)，表示走这条边会获得 \(v_i\) 的收益；若 \(v_i \lt 0\) ，则表示走这条边需要支付 \(-v_i\) 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 \(K\) 条边，然后再连接 \(K\) 条边权为 0 的边，得到一棵新的树。接着，他会选择树上的两个点 \(p,q\)，并沿着树上连接这两点的简单路径从 \(p\) 走到 \(q\)，并为经过的每条边支付过路费/ 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使总收益 - 总过路费最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的总收益 - 总过路费最大是多少。

输入格式：

输入第一行包含两个正整数 \(N,K\)。

接下来 \(N - 1\) 行，每行包含三个整数 \(x_i,y_i,v_i\)，表示第 \(i\) 条边连接图中的 \(x_i, y_i\) 两点，它的边权为 \(v_i\)。

输出格式：

输出一行一个整数，表示答案。

数据范围：

保证 \(1 \leq N \leq 3 \times 10^5\)，\(0 \leq K \leq 3 \times 10^5\)，\(K \lt N\)，\(1 \leq x_i,y_i \leq N\)，\(|v_i| \leq 10^6\)。

注意到题目相当于要求出 \(K+1\) 条不相交的链的边权和的最大值。注意单个点也算链。

设 \(f(0/1/2,u,k)\) 为 \(u\) 所在子树选 \(k\) 条链的最优解，\(u=0/1/2\) 表示在链上的度数。

当 \(u\) 的度数为 \(0\) 时，表示 \(u\) 不在选的链上，合并答案即可 \[ f_{\rm new}(0,u,i) \operatorname{\big\uparrow} f_{\rm pre}(0,u,j) + f(0,v,i - j) \]
当 \(u\) 的度数为 \(1\) 时，表示 \(u\) 为端点，考虑 \(u\) 为起点的链和 \(v\) 的链接上 \(u\) ，合并即可 \[ f_{\rm new}(1,u,i) \operatorname{\big\uparrow} \max\left\{ f_{\rm pre}(0,u,j) + f(1,v,i-j) + w(u,v),\ f_{\rm pre}(1,u,j) + f(0,v,i-j) \right\} \]
当 \(u\) 的度数为 \(2\) 时，表示 \(u\)是链中间的一点，考虑自己和儿子组链，以及儿子和儿子组链 \[ f_{\rm new}(2,u,i)\operatorname{\big\uparrow} \max\{f_{\rm pre} (1,u,j) + f(1,v,i-j-1) + w(u,v),\ f_{\rm pre}(2,u,j) + f(0,v,i-j)\} \]

这样我们就得到了一个 \(\mathcal{O}(nk)\) 的树上背包解法。

假设只选 \(K\) 条链的结果比 \(K+1\) 劣。注意到这相当于把 \(K+1\) 的一条链合并了。

显然合并的那条边贡献是非正数，否则我们 \(K+1\) 的最优方案一定会合并这两条链。

那么关于 \(k\) 的函数 \(y=f(0/1/2,u,k)\) 一定存在一个点 \(K_0\) 使得 \(K_0\) 处取到最大值。

而在 \(K_0\) 后，我们将被迫拆散很多优秀的链，这将损失很多贡献。

由此可以发现函数 \(y\) 是一个上凸函数。（好像证明的有点草率，但是能理解吧）

那么考虑 wqs 二分即可。有关 wqs 二分的具体内容可以参考之前这篇 CF739E Gosha is hunting 题解

~~如果你懒得看的话~~，简单概括一下就是，我们二分一条切线去切原函数（因为全部算出来是线性的）

然后在一番奇奇怪怪的推导之下，我们发现求出 \(y\) 相当于给每次选择物品增加了一个额外代价 \(-k\) 。

并且 wqs 二分的好处在于，它把 \(k\) 这一维省掉了，可以不考虑 \(k\) 随便选，二分会保证算出我们要的那个 \(k\)

那么不考虑 \(k\) 的话就方便多了，随便 dp 一下就好了。注意 wqs 二分到斜率相同的点时要尽可能多选。

时间复杂度 \(\mathcal{O}(n \log V)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(3e5 + 15))

int n, k, pos = 1, head[N];
struct Edge { int v, w, next; } e[N * 2];
void addEdge(int u, int v, int w) { e[++pos] = {v, w, head[u]}; head[u] = pos; }
struct qwq
{
    int x, y;
    const bool operator<(const qwq &o) const { return x == o.x ? y > o.y : x < o.x; }
    qwq operator+(const qwq &o) const { return {x + o.x, y + o.y}; }
    qwq operator+(const int &v) const { return {x + v, y}; }
    void clear() { x = 0, y = 0; }
} dp[3][N];
void up(qwq &x, const qwq &y) { x = x < y ? y : x; }
void dfs(int u, int fa, int x)
{
    up(dp[2][u], {-x, 1});
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa) continue; dfs(v, u, x);
        qwq tmp = dp[1][u] + dp[1][v] + e[i].w; tmp.x -= x; tmp.y += 1;
        up(dp[2][u], max(dp[2][u] + dp[0][v], tmp));
        up(dp[1][u], max(dp[1][u] + dp[0][v], dp[0][u] + dp[1][v] + e[i].w));
        dp[0][u] = dp[0][u] + dp[0][v];
    }
    qwq tmp = dp[1][u]; tmp.x -= x; tmp.y += 1; up(dp[0][u], max(tmp, dp[2][u]));
}
bool check(int x)
{
    rep(i, 0, 2) rep(j, 0, n + 5) dp[i][j].clear();
    dfs(1, 0, x); return dp[0][1].y <= k;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k; ++k; int sum = 0;
    for(int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w; sum += abs(w);
        addEdge(u, v, w); addEdge(v, u, w);
    }
    int l = -sum, r = sum;
    while(l < r)
    {
        int mid = (l + r) >> 1; 
        if(check(mid)) r = mid; else l = mid + 1;
    }
    check(l); cout << dp[0][1].x + l * k << '\n';
    return 0;
}