Description：

给一棵有负边的树，询问切掉 $k$ 条边再连 $k$ 条边之后树的直径的最大值。

$1\leqslant n\leqslant 3\times 10^5$

Solution：

题目等价于选 $k+1$ 条链使得链的长度最大，那么对于这种限制物品个数的问题，我们可以考虑用 $DP$ 凸优化，那么题目转变成我们要在一棵树上选一些不相交的链使得链的总长度 $+$ 链的个数 $\times C$ 最大，那么就可以设 $f[i][0/1/2]$ 表示 $i$ 这棵子树没有链经过，是一条链的结尾，在一条链的中间，然后在合并的时候 $+C$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 300010

struct edge

{

	int to,nxt,c;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

#define F 1000000000000

struct state

{

	long long val,cnt;

}f[MAXN][3];

state operator + (state a,state b){return (state){a.val + b.val,a.cnt + b.cnt};}

state operator | (state a,state b){return (state){a.val + b.val,a.cnt + b.cnt - 1};}

state operator + (state a,long long b){return (state){a.val + b,a.cnt};}

state operator - (state a,long long b){return (state){a.val - b,a.cnt};}

bool operator < (state a,state b){return (a.val == b.val ? a.cnt > b.cnt : a.val < b.val);}

long long C;

void dp(int k,int fa)

{

	f[k][2].val = f[k][1].val = C;f[k][2].cnt = f[k][1].cnt = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		dp(e[i].to,k);

		state v = max(f[e[i].to][0],max(f[e[i].to][1],f[e[i].to][2]));

		f[k][2] = max(f[k][2] + v,f[k][1] | f[e[i].to][1] + e[i].c - C);

		f[k][1] = max(f[k][1] + v,f[k][0] + f[e[i].to][1] + e[i].c);

		f[k][0] = f[k][0] + v;

	}

	return;

}

state check(long long v)

{

	C = v;

	memset(f,0,sizeof(f));

	dp(1,0);

	return max(f[1][0],max(f[1][1],f[1][2]));

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	long long l = -F,r = F,mid;

	while(l < r)

	{

		mid = floor(0.5 * (l + r + 1));

		state res = check(mid);

		if(res.cnt < m + 1)l = mid;

		else r = mid - 1;

	}

	state res = check(l);

	cout << res.val - (m + 1) * l << endl;

	return 0;

}