#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define tn long long
#define ii pair<tn,tn>
#define thaonguyenxink ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const tn N = 2e6 + 5;
struct mimi{
tn val, mn;
};
unordered_map<tn, mimi > dp;
bool check[N];
vector<ii> g[N];
tn n, u, v, k, mx_h , w, ans, sz[N];
void read(){
cin >> n >> k; ans = 1e18;
for ( tn i = 1; i < n; i++ ){
cin >> u >> v >> w;
g[u].push_back( ii( v, w ) );
g[v].push_back( ii( u, w ) );
}
}
void bfs( tn u, tn par ){
sz[u] = 1;
for ( ii v : g[u] ){
if ( v.fi == par || check[v.fi] ) continue;
bfs( v.fi , u );
sz[u] += sz[v.fi];
}
}
tn find_centroid( tn u, tn par, tn tree_sz ){
for ( ii v : g[u] )
if ( v.fi != par and !check[v.fi] and sz[v.fi] > tree_sz / 2 )
return find_centroid( v.fi , u, tree_sz );
return u;
}
void get( tn u, tn par, tn h, tn length ){
if ( length <= k )
if ( dp[k-length].val )
ans = min( ans, h + dp[k-length].mn );
for ( ii v : g[u] ){
if ( v.fi == par or check[v.fi] ) continue;
get( v.fi, u, h + 1, length + v.se );
}
}
tn compare( tn x, tn y ){
if ( !x ) return y;
return min( x, y );
}
void update( tn u, tn par, tn h, tn length ){
dp[length].val++; mx_h = max( h, mx_h );
dp[length].mn = compare( dp[length].mn, h );
for ( ii v : g[u] ){
if ( v.fi == par or check[v.fi] ) continue;
update( v.fi, u, h + 1, length + v.se );
}
}
void solve( tn u ){
bfs( u, -1 );
tn centroid = find_centroid( u, -1, sz[u] );
dp[0].val = 1; check[centroid] = 1;
for ( ii v : g[centroid] ){
if ( !check[v.fi] ){
get( v.fi, -1, 1, v.se );
update( v.fi, -1, 1, v.se );
}
}
dp.clear();
for ( ii v : g[centroid] )
if ( !check[v.fi] )
solve(v.fi);
}
signed main(){
// yêu thảo nguyên lắm á <3 <3
thaonguyenxink
read(); solve(1);
if ( ans == 1e18 ) cout << -1; else cout << ans;
}
Compilation message
/usr/bin/ld: /tmp/ccpcYOtb.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccltDKkc.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccltDKkc.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
