链接:Miku

这里是O($n^2$)的做法

首先可以证明，对于每一条直径，求出的偏心距是一样的

怎么证明？显然(我不会)

怎样求树的直径？简单。

贪心：在一条直径上，显然选择的路径越长越好

实现：首先求出树上所有点之间的距离（$n^2$）一直dfs就行

然后找出直径及直径经过的点

最后在直径上贪心的取即可

(当年的数据太water了)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int head[400];
struct b{
    int to;
    int ne;
    int v;
}e[1000];
int p;
int n,s;
int x,y,z;
int dis[400][400];
int l,r; 
int q[400];
int vis[400];
int fl;
void add(int f,int t,int v){
    p++;
    e[p].v=v;
    e[p].to=t;
    e[p].ne=head[f];
    head[f]=p;
    return ;
}
void dfs(int f,int now){
    for(int i=head[now];i;i=e[i].ne){
        if(!vis[e[i].to]){
            vis[e[i].to]=1;
            dis[f][e[i].to]=dis[f][now]+e[i].v;
            dfs(f,e[i].to);
        }
    }
}
void dfs2(int now){//把直径记录下来 
    if(vis[now]||fl)
    return ;
    vis[now]=1;
    if(now==r){
        fl=1;
        return ;
    }
    for(int i=head[now];i;i=e[i].ne){
        q[++p]=e[i].to; 
        dfs2(e[i].to);
        if(fl)
        return ;
        p--;
    }
    return ;
}
int find(){//更新 
    int ans=0;
    for(int i=1;i<=n;++i){
        if(vis[i])
        continue;
        int li=0x7ffff;
        for(int j=1;j<=n;++j){
            if(vis[j])
            li=min(li,dis[i][j]);
        }
        ans=max(li,ans);
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    }
    for(int i=1;i<=n;++i){
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        dfs(i,i);
    }
    int li=0;
    for(int i=1;i<=n;++i){
        if(dis[1][i]>li){
            li=dis[1][i];
            l=i;
        }
    }
    li=0;
    for(int i=1;i<=n;++i){
        if(dis[l][i]>li){
            li=dis[l][i];
            r=i;
        }
    }
    memset(vis,0,sizeof(vis)) ;
    p=0;
    q[++p]=l;
    dfs2(l);
    int ans=324;
    int sum=0;
    for(int i=1;i<=p;++i){
        li=0;
        sum=0;
        memset(vis,0,sizeof(vis));
        int j;
        for( j=i;j<=p&&dis[q[i]][q[j]]<=s;++j){
            vis[q[j]]=1;
        }//贪心解决 
        ans=min(ans,find()); 
    }
    cout<<ans;
    return 0;
}