思路

通过大胆猜想与小心伪证,我们可以得到一个结论:

  • 在任何一条直径求得的最小偏心距都是相等的.

有了这个结论,我们就可以乱搞啦.
对于直径,若选取的核为,最小偏心距只有可能为,,或者是选取整条直径为核时的最小偏心距.(十分好证)那么先求出某条直径的最小偏心距,然后在直径两端分别为虎一个指针,不断向中间靠拢,直到两个指针指向的节点小于为止即可.
这样复杂度就是的,可以通过.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define MAXN 305
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }
#define getchar() ( p1 == p2 && ( p1 = bf, p2 = bf + fread( bf, 1, 1 << 21, stdin ), p1 == p2 ) ? EOF : *p1++ )
char bf[1 << 21], *p1(bf), *p2(bf);
template<typename T>
inline void read( T &x ){ char t(getchar()), flg(0); x = 0;
    for ( ; !isdigit(t); t = getchar() ) flg = t == '-';
    for ( ; isdigit(t); t = getchar() ) x = x * 10 + ( t & 15 );
    flg ? x = -x : x;
}

clock_t t_bg, t_ed;
int N, S, pre[MAXN], e, mxd;
int hd[MAXN], nxt[MAXN<<1], to[MAXN<<1], val[MAXN<<1], tot(1);
inline void addedge( int x, int y, int z ){
    nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y, val[tot] = z,
    nxt[++tot] = hd[y], hd[y] = tot, to[tot] = x, val[tot] = z;
} void DFS( int u, int d ){
    if ( d > mxd ) e = u, mxd = d;
    go( i, hd[u] ) if ( i != pre[u] )
        pre[v] = i ^ 1, DFS(v, d + val[i]);
} bool bl[MAXN]; int s[MAXN], n;
void Find( int u, int fa, int d = 2333 ){
    if ( bl[u] ) d = 0;
    cmax( mxd, d );
    go( i, hd[u] ) if ( v != fa ) Find(v, u, d + val[i]);
}

int main(){
    t_bg = clock();
    read(N), read(S); int x, y, z, cur(0), sl(0), sr(0), l, r;
    fp( i, 1, N - 1 ) read(x), read(y), read(z), addedge(x, y, z);
    DFS(1, 0), mxd = 0, pre[e] = 0, DFS(e, 0);
    for ( x = e; pre[x]; x = to[pre[x]] ) bl[x] = 1, s[++n] = val[pre[x]];
    bl[x] = 1, mxd = 0, Find(e, 0); fp( i, 1, n ) cur += s[i];
    l = 1, r = n;
    while( l <= r && sl + s[l] <= mxd ) sl += s[l++];
    while( l <= r && sr + s[r] <= mxd ) sr += s[r--];
    while( l <= r && cur - sl - sr > S ){
        if ( sl + s[l] <= sr + s[r] ){
            sl += s[l++]; while( l <= r && sr + s[r] <= sl ) sr += s[r--];
        }else{
            sr += s[r--]; while( l <= r && sl + s[l] <= sr ) sl += s[l--];
        }
    } printf( "%d\n", max( max( sl, sr ), mxd ) );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}