题目描述
C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 mm 条赛道。
C 城一共有 nn 个路口，这些路口编号为 1,2,…,n1,2,…,n，有 n-1n−1 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 ii 条道路连接的两个路口编号为 a_iai 和 b_ibi，该道路的长度为 l_ili。借助这 n-1n−1 条道路，从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e_1,e_2,…,e_ke1,e2,…,ek，满足可以从某个路口出发，依次经过 道路 e_1,e_2,…,e_ke1,e2,…,ek（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的 mm 条赛道中长度最小的赛道长度最大（即 mm 条赛道中最短赛道的长度尽可能大）
输入输出格式
输入格式：
输入文件第一行包含两个由空格分隔的正整数 n,mn,m，分别表示路口数及需要修建的 赛道数。
接下来 n-1n−1 行，第 ii 行包含三个正整数 a_i,b_i,l_iai,bi,li，表示第 ii 条适合于修建赛道的道 路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n-1n−1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
输出格式：
输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。
【数据规模与约定】
对于所有的数据， 2 ≤ n ≤ 50,0002≤n≤50,000， 1 ≤ m ≤ n-11≤m≤n−1， 1 ≤ a_i,b_i ≤ n1≤ai,bi≤n， 1 ≤ l_i ≤ 10,0001≤li≤10,000。
题解：
题意即求一个k段不相交路径长度最小值的最大值；
二分这个最大的最小值mid，那么要求判断是否有一种方案可以分出>=k条路径使得权值都>=mid;
树形dp ： 当做到节点u，要么u的所有儿子都一定成为了路径，要么至多有一条可以向上延伸的路径；
这样如果可以在u形成>=mid的路径，那么一定比此时不形成路径往上连更优；
记录每个点可以往上连的权值val，考虑u的儿子v，u,v之间的边为E[i] （代码风格，忍受一下。。）
val[v]+E[i].w >= mid 直接统计为一条合法路径；
否则把左边存在一个数组里，可以知道要形成路径只能两两配对，排序后二分可以确定最大的对数；
注意未配对的最大的数可能可以替换已配对的权值，找到最大可替换数设置成val[u](注意细节)
复杂度 $O(n log^2 n)$
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define inf 0x3f3f3f3f
#define rg register
#define il inline
#define Run(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int N=;
int n,k,o,hd[N],mid,val[N],sum,p[N];
vector<int>g[N];
struct Edge{int v,nt,w;}E[N<<];
void adde(int u,int v,int w){
E[o]=(Edge){v,hd[u],w};hd[u]=o++;
E[o]=(Edge){u,hd[v],w};hd[v]=o++;
}
bool check2(int u,int Mid){
int cnt=g[u].size();
int p=cnt-(Mid<<);
for(int i=;i<=Mid;i++){
if(g[u][p+i-]+g[u][cnt-i]<mid)return false;
}
return true;
}
void dfs(int u,int fa){
g[u].clear();
val[u]=;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa)continue;
dfs(v,u);
int t=E[i].w+val[v];
if(t>=mid)sum++;
else g[u].push_back(t);
}
int cnt=(int)g[u].size();
if(!cnt)return;
sort(g[u].begin(),g[u].end());
int l=,r=cnt>>;
while(l<r){
int Mid=(l+r+)>>;
if(check2(u,Mid))l=Mid;
else r=Mid-;
}
sum+=l;
if((l<<)==cnt)return;
for(int i=;i<l;i++){
int t1=cnt-(l<<)+i;
int t2=cnt--i;
p[t1]=t2;
p[t2]=t1;
}
int t;
for(t=cnt-(l<<);t<cnt&&g[u][t-]+g[u][p[t]]>=mid;t++){
p[p[t]]=t-;
p[t-]=p[t];
}
t--;
return void(val[u]=g[u][t]);
}
bool check1(){
sum=;dfs(,);
return sum>=k;
}
int main(){
freopen("track.in","r",stdin);
freopen("track.out","w",stdout);
scanf("%d%d",&n,&k);
int l=inf,r=;
o=;
for(rg int i=,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
r+=w; l=min(l,w);
adde(u,v,w);
}
while(l<r){
mid=(l+r+)>>;
if(check1())l=mid;
else r=mid-;
}
printf("%d\n",l);
}//by tkys_Austin;