记录编号	540331	评测结果	AAAAAAAAAAAWWWWWWWWW
题目名称	[NOIP 2018]赛道修建	最终得分	55
用户昵称	ShallowDream雨梨	是否通过	未通过
代码语言	C++	运行时间	0.127 s
提交时间	2019-08-20 19:29:10	内存使用	15.62 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long 
using namespace std;
const int maxn=50005;
int sum,juhua=0,lian[maxn],lian_,q,w,e[maxn],n,m;//n_dian,m_saidao
int node,tot,head[maxn],ans[maxn],ans_;
bool vis[maxn];
struct road{int to,next,v;}a[maxn*2];
inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}
void add(int q,int w,int e){
	tot++;
	a[tot].to=w;
	a[tot].v=e;
	a[tot].next=head[q];
	head[q]=tot;}
void dfs(int x,int fa){
	for(int i=head[x];i;i=a[i].next){
	int qwq=a[i].to;
	if(vis[qwq]==1||qwq==fa)continue;
		vis[qwq]=1;
		ans[qwq]=ans[x]+a[i].v;
		if(ans[qwq]>ans_){
		node=qwq;
		ans_=ans[qwq];}
		dfs(qwq,x);
	}}
	void dfs_lian(int x,int fa){
	for(int i=head[x];i;i=a[i].next){
		int qwq=a[i].to;
		if(qwq==fa)continue;
	
		dfs_lian(qwq,x);	lian[x]=a[i].v;
		}
	}
 int check(int k){
        int t=0,now=0;
        for(int i=1;i<n;i++){
            if(now+lian[i]>=k){
                now=0;
                t++;
            }
            else now+=lian[i];
        }
        return t>=m;
    }
int cmp1(int q,int w){return q>w;}
//int cmp2(road e,road r){return e.to<r.to;}
int main(){
		freopen("2018track.in","r",stdin);
		freopen("2018track.out","w",stdout);


	n=read();m=read();
	for(int i=1;i<n;i++){
q=read();w=read();e[i]=read();
		if(q==1)juhua++;
		if(w==q+1)lian_++;
		add(q,w,e[i]);
		add(w,q,e[i]);
		sum+=e[i];}

		if(m==1){
		dfs(1,0);
		memset(ans,0,sizeof(ans));
		memset(vis,0,sizeof(vis));
		ans_=0;
		dfs(node,0);
		cout<<ans_;
		return 0;}
		
		if(juhua==n-1){
		sort(e+1,e+n,cmp1);
		ans_=99999999;
		for(int i=1;i<=m;i++)
		ans_=min(ans_,e[i]+e[2*m-i+1]);
		cout<<ans_;
		return 0;}
		
		if(lian_==n-1){	
			int ans;
		dfs_lian(1,0);
		int l=1,r=sum,mid;
		while(l<=r){
		mid=(l+r)/2;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;}
		cout<<ans;}
	return 0;
}