弄了一晚上，几篇博客交换看才看懂。

可能也是因为分心了的缘故。

Solution

将整棵树分为 $k+1$ 个联通块，对每个联通块找直径，然后直径端点连成一条链一定是最优解。

考虑转化问题，求树上 $k+1$ 条不相交链的最大权和。

设计状态。考虑一个点的度数只可能为 $0/1/2$ 。令 $f_{i, j, k}$ 为第 $i$ 个点，度数为 $j$ ，用了 $k$ 条链的子树最优解。

再具体阐述状态。$f_{i, 0}$ 代表这个点度数为 $0$ ，即在最终的方案中它并不属于直径，因此不占用任何链的个数也不提供任何贡献。 $f_{i, 1}$ 的状态正常。 $f_{i, 2}$ 代表这个点的度数为 $2$ 。那么如果我们想要一个单点成为直径中的一条链，我们就假设是 $i$ 向自己连了自环，度数为 $2$ 且占用了一条链的数目。

那么初始化也就呼之欲出了：$f_{i, 0, 0}=f_{i, 2, 1}=0$ ，其余置为 $-\infty$ 。

转移不难。

通过观察（打表）发现对于使用链数为 $k$ 的最优解呈凸函数，使用 凸优化dp 来去除 $k$ 的限制。

注意我们是对每条链产生的贡献减去斜率而不是对每条边。

那么初始的dp去除第三维来做就行了。

但是凸函数可能会出现你要找的点和前后两点处于同一直线。那么此时应当二分到该直线的斜率，并使用斜率和 $k$ 来直接求出 $k$ 的最优值。

Code

// Code by ajcxsu
// Problem: linke kate shu

#include<bits/stdc++.h>
#define INF (0x7fffffff)
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=ch=='-', ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
template<typename T, typename ...Args> inline void gn (T &x, Args &...args) {
    gn(x), gn(args...);
}

const int N=3e5+10, M=N<<1;
typedef long long ll;
struct Data {
    ll x; int k;
    friend bool operator < (const Data &a, const Data &b) { return a.x==b.x?(a.k<b.k):a.x<b.x; }
    Data operator + (const Data &b) { return {x+b.x, k+b.k}; }
} f[3][N], tmp[3];
int h[N], to[M], nexp[M], p=1;
ll W[M], rw[M];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
ll delta;
void dfs(int x, int fr) {
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr) {
            dfs(to[u], x);
            for(int i=0; i<3; i++) tmp[i]={-(1ll<<60), 0x3f3f3f3f};
            for(int i=0; i<3; i++) tmp[0]=max(tmp[0], f[0][x]+f[i][to[u]]);
            tmp[1]=max(f[0][x]+f[0][to[u]]+(Data){W[u]-delta, 1}, f[0][x]+f[1][to[u]]+(Data){W[u], 0});
            for(int i=0; i<3; i++) tmp[1]=max(tmp[1], f[1][x]+f[i][to[u]]);
            tmp[2]=max(f[1][x]+f[0][to[u]]+(Data){W[u], 0}, f[1][x]+f[1][to[u]]+(Data){W[u]+delta, -1});
            for(int i=0; i<3; i++) tmp[2]=max(tmp[2], f[2][x]+f[i][to[u]]);
            for(int i=0; i<3; i++) f[i][x]=tmp[i];
        }
}

int n;
int check(ll v) {
    delta=v;
    for(int i=1; i<=n; i++) f[0][i]={0, 0}, f[1][i]={-(1ll<<60), 0x3f3f3f3f}, f[2][i]={-v, 1};
    dfs(1, 0);
    return max({f[0][1], f[1][1], f[2][1]}).k;
}

int main() {
    int k;
    gn(n), gn(k); k++;
    int u, v, w;
    ll l=0, r=0, mid, ans=-INF;
    for(int i=0; i<n-1; i++) gn(u, v, w), ins(u, v, w), ins(v, u, w), r+=abs(w);
    l=-r;
    memcpy(rw, W, sizeof(W));
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid)>=k) l=mid+1, ans=mid;
        else r=mid-1;
    }
    check(ans);
    printf("%lld\n", max({f[0][1], f[1][1], f[2][1]}).x+ans*k);
    return 0;
}