#include <bits/stdc++.h> #define ll long long #define pii pair < int, int > #define F first #define S second #define mp make_pair #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; const int N = 2e5+10, K = 1e6+10, inf = 1e9+10; int n, k; vector < pii > adj[N]; bool turnedoff[N]; int distfound[K]; int siz[N]; void dfs( int x, int par ) { int sus; siz[x] = 1; for(int i = 0; i < (int) adj[x].size(); i++) { sus = adj[x][i].F; if(sus != par && !turnedoff[sus]) { dfs(sus, x); siz[x] += siz[sus]; } } return; } int find_centroid( int x, int par, int reqsiz ) { int sus; pii maxi = mp(0, -1); for(int i = 0; i < (int) adj[x].size(); i++) { sus = adj[x][i].F; if(sus != par && !turnedoff[sus]) { maxi = max(maxi, mp(siz[sus], sus)); } } if(maxi.F <= reqsiz) return x; return find_centroid(maxi.S, x, reqsiz); } int query_dfs( int x, int par, bool doset, bool v, int curv, int curdep ) { // cout << x << " " << curv << " " << curdep << "\n"; int sus; if(curv > k) return inf; if(doset) { if(!v) distfound[curv] = inf; else distfound[curv] = min(distfound[curv], curdep); } int out = inf; out = min(out, distfound[k - curv] + curdep); for(int i = 0; i < (int) adj[x].size(); i++) { sus = adj[x][i].F; if(sus != par && !turnedoff[sus]) { out = min(query_dfs(sus, x, doset, v, curv + adj[x][i].S, curdep + 1), out); } } return out; } int cd( int root ) { dfs(root, root); int centr = find_centroid(root, root, siz[root] / 2); turnedoff[centr] = 1; int out = inf; int sus; for(int i = 0; i < (int) adj[centr].size(); i++) { sus = adj[centr][i].F; if(!turnedoff[sus]) { out = min(out, query_dfs(sus, sus, 0, 0, adj[centr][i].S, 1)); query_dfs(sus, sus, 1, 1, adj[centr][i].S, 1); } } // cout << centr << ":\n"; // for(int i = 0; i <= k; i++) cout << distfound[i] << " "; // cout << "\n\n"; // cout << out << "\n\n"; // query_dfs(centr, centr, 1, 0, 0, 0); out = min(out, distfound[k]); query_dfs(centr, centr, 1, 0, 0, 0); for(int i = 0; i < (int) adj[centr].size(); i++) { sus = adj[centr][i].F; if(!turnedoff[sus]) { out = min(out, cd(sus)); } } // cout << out << "\n"; return out; } int task( void ) { // cin >> n >> k; // for(int i = 0; i < n; i++) adj[i].clear(); // for(int i = 0; i < n; i++) turnedoff[i] = 0; for(int i = 0; i <= k; i++) distfound[i] = inf; /* int a, b, c; for(int i = 0; i < n - 1; i++) { cin >> a >> b >> c; adj[a].pb(mp(b, c)); adj[b].pb(mp(a, c)); }*/ int sol = cd(0); // cout << sol << "\n"; if(sol != inf) return sol; else return -1; } int best_path( int nn, int kk, int hh[][2], int l[] ) { for(int i = 0; i < nn - 1; i++) { adj[hh[i][0]].pb(mp(hh[i][1], l[i])); adj[hh[i][1]].pb(mp(hh[i][0], l[i])); } n = nn; k = kk; return task(); }