题目分析

题意理解

我们有一棵树，可以切掉恰好 K 条边，然后连接 K 条权值为0的边，形成一棵新树。然后选择一条路径，求路径上边权和的最大值。

关键转化：切掉 K 条边相当于将原树分成 K+1 个连通块，然后在块间添加边权为0的边。问题转化为在树中选择 K+1 条不相交的路径，使得路径权值和最大。

问题重述

求在树上选择恰好 K+1 条边不相交的路径，使得这些路径的权值和最大。

算法思路

整体框架：wqs二分 + 树形DP

1. wqs二分（带权二分）

对于"恰好选择K+1条路径"这个约束，使用wqs二分：

• 给每条路径一个附加代价 λ
• 二分λ，使得最优解恰好选择K+1条路径
• 最终答案 = 最大权值和 + λ×(K+1)

2. 树形DP状态设计

对于每个节点x，定义三个状态：

• f[x][0]：x的子树中，x不在任何路径上的最大权值和
• f[x][1]：x的子树中，x是某条路径端点的最大权值和
• f[x][2]：x的子树中，x是某条路径中间点的最大权值和

代码详解

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

namespace run {
const int maxn = 3e5 + 10;

// 边结构
struct Edge {
    int nxt, to, w;
} edge[maxn << 1];
int begn[maxn], e;

inline void add(int x, int y, int z) {
    edge[++e] = (Edge){begn[x], y, z};
    begn[x] = e;
    return;
}

// DP状态结构体
struct DP {
    ll f;       // 最大权值和
    int num;    // 路径数量
    
    DP(ll F = 0, int Num = 0) {
        f = F;
        num = Num;
    }
    
    // 比较函数：优先比较权值，再比较路径数
    bool operator < (const DP &rhs) const {
        return (f ^ rhs.f) ? f < rhs.f : num < rhs.num;
    }
} I, f[maxn][3];  // I: wqs二分的代价

// DP状态合并
DP operator + (DP x, DP y) {
    return DP(x.f + y.f, x.num + y.num);
}

// 树形DP
inline void dfs(int x, int fa) {
    // 初始化状态
    f[x][0] = f[x][1] = DP(0, 0);  // 0: 不在路径, 1: 路径端点
    f[x][2] = I;                   // 2: 路径中间点，初始化为代价I
    
    // 遍历所有子节点
    for (int i = begn[x]; i; i = edge[i].nxt) {
        int y = edge[i].to;
        if (y == fa) continue;
        
        dfs(y, x);
        DP tmp = DP(edge[i].w, 0);  // 当前边的权值
        
        // 更新f[x][2]: x作为路径中间点
        // 情况1: x连接两条路径 (x作为中间点连接两个子树的路径)
        f[x][2] = max(f[x][2], f[x][1] + tmp + f[y][1] + I);
        // 情况2: x继续作为中间点，y不在路径
        f[x][2] = max(f[x][2], f[x][2] + f[y][0]);
        
        // 更新f[x][1]: x作为路径端点  
        // 情况1: x连接一条路径 (x与y的路径连接)
        f[x][1] = max(f[x][1], f[x][0] + f[y][1] + tmp);
        // 情况2: x继续作为端点，y不在路径
        f[x][1] = max(f[x][1], f[x][1] + f[y][0]);
        
        // 更新f[x][0]: x不在任何路径
        f[x][0] = max(f[x][0], f[x][0] + f[y][0]);
    }
    
    // 最终合并：选择最优状态
    f[x][0] = max(f[x][0], max(f[x][1] + I, f[x][2]));
}

int n, K;
ll ans;

inline bool main() {
    read(n, K);
    ++K;  // 切K条边 => 选择K+1条路径
    
    // 建树
    for (int i = 1, x, y, z; i < n; ++i) {
        read(x, y, z);
        add(x, y, z);
        add(y, x, z);
    }
    
    // wqs二分
    int l = -1e8, r = 1e8;  // 二分范围
    
    while (l + 1 < r) {
        int mid = ((l + r) >> 1);
        I = DP(-mid, 1);  // 设置每条路径的代价
        
        dfs(1, 0);  // 进行树形DP
        
        if (f[1][0].num >= K) {
            // 路径数过多，需要增加代价
            l = mid;
            ans = f[1][0].f + 1ll * mid * K;
        } else {
            // 路径数不足，需要减少代价  
            r = mid;
        }
        
        // 如果恰好找到K条路径，提前退出
        if (f[1][0].num == K)
            break;
    }
    
    printf("%lld\n", ans);
    return 0;
}
}

int main() {
    return run::main();
}

算法核心要点详解

1. 树形DP状态转移

状态定义：

• f[x][0]：x不在任何路径上
• f[x][1]：x是某条路径的端点
• f[x][2]：x是某条路径的中间点

关键转移：

f[x][2]的更新：

// 情况1: x连接两条路径
f[x][2] = max(f[x][2], f[x][1] + tmp + f[y][1] + I);
// x作为端点 + 边权 + y作为端点 + 路径代价
// 这样x就变成了中间点，路径数+1

// 情况2: x继续作为中间点
f[x][2] = max(f[x][2], f[x][2] + f[y][0]);

f[x][1]的更新：

// 情况1: x连接一条路径  
f[x][1] = max(f[x][1], f[x][0] + f[y][1] + tmp);
// x不在路径 + y作为端点 + 边权 = x成为端点

// 情况2: x继续作为端点
f[x][1] = max(f[x][1], f[x][1] + f[y][0]);

2. wqs二分原理

核心思想：通过给每条路径添加代价λ，控制选择的路径数量。

• λ越大：选择路径的代价越大，倾向于选择更少的路径
• λ越小：选择路径的代价越小，倾向于选择更多的路径

通过二分找到使路径数恰好为K+1的λ值。

3. 最终答案计算

ans = f[1][0].f + 1ll * mid * K;

这里加上 mid * K 是因为在DP过程中我们减去了K次mid代价，现在要加回来。

复杂度分析

• 树形DP：O(n)
• wqs二分：O(log V)，其中V是值域
• 总复杂度：O(n log V)，可以处理n=3×10⁵

举例说明

以样例为例：

输入: 
5 1
1 2 3
2 3 5  
2 4 -3
4 5 6

K=1 => 选择2条路径
最优解：路径1→2→3 和 路径4→5
权值和 = (3+5) + 6 = 14

总结

这道题综合运用了：

1. 问题转化：将切边问题转化为选择不相交路径问题
2. 树形DP：设计复杂状态处理路径连接
3. wqs二分：处理"恰好选择K条"的约束条件
4. 状态合并：巧妙处理各种路径连接情况

是一个很好的树形DP与wqs二分结合的经典题目。