一看这种题就不是lct。。。
除了直径好拿分，别的都难做。
所以必须转化
突破口在于：连“0”边
对于k=0，我们求直径
k=1，对于(p,q)一定是从p出发，走一段原树，走0（或不走），再走一段原树，所以要最大化原树的值的和。
选择最大两条 点不相交的链（注意：可以选择一个点，这时候链长为0）。然后一定可以首尾连起来得到答案
k更大的时候，选择最大的k+1条两两不相交的路径，然后一定存在方案使之连接起来，一定是最优解。（因为如果实际上最优解不用走k条0边，一定会把这些0边随便连一连废掉，对应选择一个点作为链）
所以，求最大的k+1条两两点不相交的路径。
点不相交，每次贪心取直径然后取反其实不好做。而且显然扩展性太差
树形DP
f[x][0/1/2][k]表示x为根的子树，从下面连接到x的度数是0/1/2，用k条链的最优解。特别地，从x开始往上的链归入f[x][1][*]。
转移时候枚举和当前儿子怎么连就好了。
看上去已经不能优化了。
然鹅
可以发现，如果f[x]函数表示选择x个链的最大总和
这是一个上凸函数！
就可以WQS二分了
具体地，每个链的额外花费mid的代价
然后求全局的最高点。没了k的限制就好做了
f[x][0/1/2]
（PS：
1.这个题如果连接的新边不是0应该也可以，但是必须是正数，负数的话转化就不对了，不一定走K次新边最优
2.如果k是一个区间也许也可以？
）
代码：
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;x=;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=3e5+;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,k;
int b[N][];
struct node{
int nxt,to;
ll val;
}e[*N];
int hd[N],cnt;
void add(int x,int y,ll z){
e[++cnt].nxt=hd[x];
e[cnt].val=z;
e[cnt].to=y;
hd[x]=cnt;
}
struct dp{
ll v;
int c;
dp(){}
dp(ll a,int b){
v=a;c=b;
}
dp operator +(const dp &b){
return dp(v+b.v,c+b.c);
}
bool friend operator <(dp a,dp b){
return (a.v<b.v||(a.v==b.v&&a.c<b.c));
}
void clear(){
v=-inf;c=-0x3f3f3f3f;
}
}f[N][];
ll sum;
void dfs(int x,int fa,ll mid){
f[x][].clear();
f[x][].clear();
f[x][].v=,f[x][].c=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
dfs(y,x,mid);
f[x][]=max(f[x][]+f[y][],f[x][]+f[y][]+dp(e[i].val+mid,-));
f[x][]=max(f[x][]+f[y][],f[x][]+f[y][]+dp(e[i].val,));
f[x][]=f[x][]+f[y][];
}
f[x][]=max(f[x][],f[x][]+dp(-mid,));
f[x][]=max(f[x][],max(f[x][],f[x][]));
}
int check(ll mid){
memset(hd,,sizeof hd);cnt=;
sum=;
for(reg i=;i<n;++i){
add(b[i][],b[i][],b[i][]);
add(b[i][],b[i][],b[i][]);
}
dfs(,,mid);
// for(reg i=1;i<=n;++i){
// cout<<" i "<<i<<" : "<<f[i][0].v<<" "<<f[i][0].c<<endl;
// }
sum=f[][].v;
// cout<<" mid "<<mid<<" :: "<<sum<<" "<<f[1][0].c<<endl;
return f[][].c;
}
int main(){
rd(n);rd(k);
++k;
ll l=,r=;
for(reg i=;i<n;++i){
rd(b[i][]);rd(b[i][]);rd(b[i][]);
r+=abs(b[i][]);
}l=-r;
ll ans=-;
while(l<=r){
ll mid=(l+r)/;
if(check(mid)>=k) ans=mid,l=mid+;
else r=mid-;
}
int haha=check(ans);
printf("%lld\n",sum+(ll)k*ans);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/20 15:23:18
*/
总结：
1.转化为k+1个链
2.树形dp（经典问题）
3.凸函数，WQS二分