赛道修建

题目描述

C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建

C 城一共有 $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（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。$

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的

输入格式

输入文件第一行包含两个由空格分隔的正整数

接下来 $a_i,b_i,l_iai,bi,li，表示第 ii 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n-1n−1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。$

输出格式

输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

【输入输出样例 1 说明】

所有路口及适合于修建赛道的道路如下图所示：

道路旁括号内的数字表示道路的编号，非括号内的数字表示道路长度。需要修建

【输入输出样例 2 说明】

所有路口及适合于修建赛道的道路如下图所示：

需要修建

经过第
经过第
经过第

【数据规模与约定】

所有测试数据的范围和特点如下表所示 :

其中，“分支不超过 $a_i,b_i ≤ n1≤ai,bi≤n， 1 ≤ l_i ≤ 10,0001≤li≤10,000。$

玄学DFS第二弹：

其实MAP是能拿满分的，但是我代码找不到了。。。。。。

#include<cstdio>
#include<algorithm>
#include<cstring>

#define re register

using namespace std;

inline int read()
{
    int x=0;
    char ch=getchar();
    char c=ch;
    while(ch>'9'||ch<'0')c=ch,ch=getchar();
    while(ch<='9'&&ch>= '0')x=x*10+ch-'0',ch=getchar();
    if(c=='-')x=x*-1;
    return x;
}

inline void put(int x)
{
    if(x<0) putchar('-'),x=~x+1;
    if(x>9) put(x/10);
    putchar(x%10+'0');
}

const int N=5e5+5;

struct node{
    int y,z,nxt;
}a[N*2];

int len,last[N];

inline void add(int x,int y,int z){
    a[++len].y=y;
    a[len].z=z;
    a[len].nxt=last[x];
    last[x]=len;
}
int n,m,mid,now;

int f[N];

inline void dfs(int x,int fa){
    for(int k=last[x];k;k=a[k].nxt){
        if(a[k].y!=fa){
            dfs(a[k].y,x);
        }
    }
    int st[N],tp=0;
    for(int k=last[x];k;k=a[k].nxt){
        if(a[k].y!=fa){
            st[++tp]=f[a[k].y]+a[k].z;
        }
    }
    sort(st+1,st+tp+1);
    while(tp&&st[tp]>=mid){
        tp--;
        now++;
    }
    for(int i=1;i<=tp;++i){
        while(st[i]+st[tp]>=mid&&i<tp){
            now++;
            tp--;
            i++;
        }
    }
    if(tp){
        f[x]=st[tp];
    }
}
inline bool check(){
    now=0;
    dfs(1,0);
    if(now>=m){
        return true;
    }
    return false;
}
int main(){
    n=read();
    m=read();
    int l=0x3f3f3f3f,r=0,ans=0;
    for(int i=1;i<n;++i) {
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);r+=z;l=min(l,z);
    }
    while(l<=r){
        mid=(l+r)>>1;
        memset(f,0,sizeof(f));
        if(check()){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }  
    put(ans);
    putchar('
');
    return 0;
}