题目：赛道修建
思路：
二分答案。
judge时，令节点1为根节点，dfs求解。
安利
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 50000
#define read(x) scanf("%d",&x)int cnt[maxn+5],f[maxn+5];struct Edge{
int u,v,w,f;Edge(){
}Edge(int uu,int vv,int ww) {
u=uu,v=vv,w=ww;}Edge(Edge oth,int ff) {
u=oth.u,v=oth.v,w=oth.w,f=ff;}bool operator < (const Edge& oth) const {
return f<oth.f;}
};int n,m;vector<Edge> g[maxn+5];vector<Edge> chd[maxn+5];void dfs(int x,int fa,int mid) {
cnt[x]=f[x]=0;chd[x].clear();for(int i=0;i<g[x].size();i++) {
Edge y=g[x][i];if(y.v==fa) continue;dfs(y.v,x,mid);f[y.v]+=y.w;if(f[y.v]>=mid) cnt[x]++;else chd[x].push_back(Edge(y,f[y.v]));}if(chd[x].size()==0) {
return ;}sort(chd[x].begin(),chd[x].end());int L=0,R=chd[x].size()-1,mm=-1,dd=0;while(L<R) {
if(chd[x][L].f+chd[x][R].f>=mid) cnt[x]++,dd++,L++,R--;else L++; }L=0,R=chd[x].size()-1;while(L<=R) {
int Mid=(L+R)/2;int flg=0;int l=0,r=chd[x].size()-1;if(l==Mid) l++;if(r==Mid) r--;while(l<r) {
if(chd[x][l].f+chd[x][r].f>=mid) flg++,l++,r--;else l++;if(l==Mid) l++;if(r==Mid) r--;}if(flg==dd) L=Mid+1,mm=Mid;else R=Mid-1;}if(mm!=-1) f[x]=max(f[x],chd[x][mm].f);return ;
}bool judge(int mid) {
int ans=0;dfs(1,0,mid);for(int i=1;i<=n;i++) ans+=cnt[i];return ans>=m;
}int main() {
int L=0,R=0;read(n),read(m);for(int i=1;i<n;i++) {
int x,y,z;read(x),read(y),read(z);R+=z;g[x].push_back(Edge(x,y,z)),g[y].push_back(Edge(y,x,z));}R/=m;int ans;while(L<=R) {
int mid=(L+R)/2;if(judge(mid)) L=mid+1,ans=mid;else R=mid-1;}printf("%d",ans);return 0;
}