对拍自取。
#include<bits/stdc++.h>
using namespace std;
inline bool rd ( int &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline bool lrd ( long long &k ){
char c = getchar ();
bool neg = false;
while ( c != EOF && c != '-' && ( c < '0' || c > '9' ) )
c = getchar ();
if ( c == EOF ) return false;
if ( c == '-' ){
neg = true;
k = 0;
}else
k = c - '0';
c = getchar ();
while ( c >= '0' && c <= '9' ){
k = ( k << 1 ) + ( k << 3 ) + c - '0'; c = getchar ();
}
if ( neg ) k = -k;
return true;
}
inline void freo (){
freopen ( "data.in", "r", stdin );
freopen ( "data.out", "w", stdout );
}
const int N = 500001;
const int M = 1000001;
const int INF = 0x3f3f3f3f;
int vtot, pre [N], dia_tot;
int dis_in [N], dis_out [N], max_dis;
int dir [M], hed [N], val [M], dia [N], etot, nxt [M];
bool vis [N];
inline void new_e ( int u, int v, int k ){
int i = ++etot;
dir [i] = v;
val [i] = k;
nxt [i] = hed [u];
hed [u] = i;
}
inline void bfs ( int start, bool use_pre ){
for ( int i = 1; i <= vtot; ++i ) dis_in [i] = INF;
queue <int> q;
dis_in [start] = 0;
q.push (start);
while ( q.size () ){
int from = q.front (); q.pop ();
for ( int i = hed [from]; i; i = nxt [i] ){
int to = dir [i];
if ( dis_in [to] != INF ) continue;
dis_in [to] = dis_in [from] + val [i];
if ( use_pre ) pre [to] = from;
q.push (to);
}
}
}
inline void diameter (){
bfs ( 1, false );
int start = 1;
for ( int i = 2; i <= vtot; ++i )
if ( dis_in [i] > dis_in [start] )
start = i;
bfs ( start,true );
int end = start;
for ( int i = 1; i <= vtot; ++i )
if ( dis_in [i] > dis_in [end] )
end = i;
int temp = end;
while ( temp ){
dia [++dia_tot] = temp;
temp = pre [temp];
}
}
inline void dfs ( int from ){
for ( int i = hed [from]; i; i = nxt [i] ){
int to = dir [i];
if ( vis [to] ) continue;
vis [to] = true;
dfs ( to );
dis_out [from] = max ( dis_out [from], dis_out [to] + val [i] );
}
}
inline int farthest (){
for ( int i = 0; i <= dia_tot; ++i )
vis [ dia[i] ] = true;
for ( int i = 0; i <= dia_tot; ++i )
dfs ( dia[i] );
int out = -INF;
for ( int i = 1; i <= dia_tot; ++i )
out = max ( out, dis_out [ dia[i] ] );
return out;
}
int main (){
rd ( vtot );
rd ( max_dis );
for ( int i = 1; i < vtot; ++i ){
int u, v;
int k;
rd ( u ); rd ( v );
rd ( k );
new_e ( u, v, k );
new_e ( v, u, k );
}
diameter ();
int max_out = farthest ();
int min_ecc = INF;
for ( int first = 1, second = 1; second <= dia_tot; ++first ){
int first_node = dia [first];
int second_node = dia [second];
while ( second <= dia_tot && abs ( dis_in [first_node] - dis_in [second_node] ) <= max_dis ){
min_ecc = min ( min_ecc, max ( max_out,
max ( abs(dis_in[dia[1]]-dis_in[first_node]), abs (dis_in[dia[dia_tot]]-dis_in[second_node]) ) ) );
second ++;
second_node = dia [second];
}
}
printf ( "%d", min_ecc ); return 0;
}
没有讲解,可能以后会有。
(小声ACAC,时空限制好严格)