#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
void prepare(); void main_code();
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const bool MULTITEST = 0; prepare();
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); }
}
void prepare(){};
int n, k;
vec<ii> g[N];
bool on[N];
int s[N];
void init(int u, int p) {
s[u] = 1;
for(auto [v,w] : g[u]) if (on[v] and v != p) {
init(v, u);
s[u] += s[v];
}
}
int centroid(int u, int p, int t) {
for(auto [v,w]:g[u])if(on[v] and v!=p and s[v]>t/2)
return centroid(v,u,t);
return u;
}
int ans = 0;
multiset<int> d[5 * N];
void DFS(int u, int par, bool t, int dis, int dx) {
if (dis > k) return ;
if (t == 0) {
if (sz(d[k - dis])) {
ans = min(ans, dx + *d[k - dis].begin());
}
} else if (t == 1) {
d[dis].insert(dx);
} else
d[dis].erase(d[dis].find(dx));
for(auto [v,w] : g[u]) if (v != par and on[v]) {
DFS(v, u, t, dis + w, dx + 1);
}
}
void calc(int u) {
d[0].insert(0);
for(auto [v,w] : g[u]) if (on[v]) {
DFS(v,u,0,w, 1);
DFS(v,u,1,w, 1);
}
for(auto [v,w] : g[u]) if (on[v]) {
DFS(v,u,-1,w, 1);
}
d[0].erase(0);
}
void solve(int u) {
init(u, 0);
u = centroid(u, 0, s[u]);
calc(u);
on[u] = 0;
for(auto [v,w] : g[u]) if (on[v]){
solve(v);
}
}
void main_code() {
cin >> n >> k;
ans = n + 1;
FOR(i, 1, n) on[i] = 1;
FOR(i, 2, n) {
int u, v, w; cin >> u >> v >> w;
++u, ++v;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
solve(1);
if (ans == n + 1) ans = -1;
cout << ans;
}
/* Let the river flows naturally */
Compilation message
race.cpp: In function 'void init(int, int)':
race.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | for(auto [v,w] : g[u]) if (on[v] and v != p) {
| ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
58 | for(auto [v,w]:g[u])if(on[v] and v!=p and s[v]>t/2)
| ^
race.cpp: In function 'void DFS(int, int, bool, int, int)':
race.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for(auto [v,w] : g[u]) if (v != par and on[v]) {
| ^
race.cpp: In function 'void calc(int)':
race.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for(auto [v,w] : g[u]) if (on[v]) {
| ^
race.cpp:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for(auto [v,w] : g[u]) if (on[v]) {
| ^
race.cpp: In function 'void solve(int)':
race.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [v,w] : g[u]) if (on[v]){
| ^
race.cpp: In function 'int main()':
race.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBGa0ub.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczXY709.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cczXY709.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
