#include "race.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
// g++ -std=c++11 -Wall -Wextra -O2 -pipe grader.cpp cluedo.cpp -o cluedo && cluedo < grader.in.1
set<pii> adj[200000]; // node, length
int subt_sz[200000];
int dfs_sz(int x, int p) {
subt_sz[x] = 1;
for (auto c : adj[x]) if (c.first != p) subt_sz[x] += dfs_sz(c.first, x);
return subt_sz[x];
}
int getCentroid(int x, int p) {
dfs_sz(x, p);
int maxsize = subt_sz[x]/2;
while (true) {
int next = -1;
for (auto c : adj[x]) if (c.first!=p && subt_sz[c.first] > maxsize) {
next = c.first;
break;
}
if (next == -1) return x;
p = x, x = next;
}
assert(0);
}
int ans = INT_MAX, LN; // min highways, with len = LN
void dfs_subt(int x, int p, int len, int highways, map<int,int> &table){
if(table.find(len) == table.end()) table[len] = highways;
else minn(table[len], highways);
for(auto c : adj[x]) if(c.first != p && len+c.second <= LN)
dfs_subt(c.first, x, len+c.second, highways+1, table);
}
void dfsSolve(int root) {
//cout << "initial root = " << root << endl;
root = getCentroid(root, -1);
//cout << "centroid = " << root << endl;
map<int, multiset<int>> table; // <len, possible highways>
v<map<int,int>> subdata; // {len, highways}
for(auto subt : adj[root]){
subdata.push_back(map<int,int>());
dfs_subt(subt.first, root, subt.second, 1, subdata.back());
//cout << "subt " << subt.first << " data " << endl;
// for(auto pp : subdata.back())
//cout << "len " << pp.first << "; highways " << pp.second << endl;
for(auto pp : subdata.back())
table[pp.first].insert(pp.second);
}
for(auto &subtable : subdata){
for(auto pp : subtable)
table[pp.first].erase(table[pp.first].find(pp.second));
for(auto pp : subtable){
if(pp.first == LN){
minn(ans, pp.second);
//cout << "ans (single) " << pp.second << endl;
}
else
if(table.find(LN-pp.first) != table.end() && table[LN-pp.first].size() > 0){
minn(ans, pp.second + *table[LN-pp.first].begin());
//cout << "ans " << (pp.second) << " + " << *table[LN-pp.first].begin() << endl;
}
}
for(auto pp : subtable)
table[pp.first].insert(pp.second);
}
//cout << endl << endl;
for (auto subt : adj[root]) {
assert(adj[subt.first].find({root, subt.second}) != adj[subt.first].end());
adj[subt.first].erase({root, subt.second});
dfsSolve(subt.first);
}
}
void add_edge(int a, int b, int c){
adj[a].insert({b,c});
adj[b].insert({a,c});
}
int best_path(int N, int K, int H[][2], int L[]){
FOR(i,0,N-1)
add_edge(H[i][0], H[i][1], L[i]);
LN = K;
dfsSolve(0);
return (ans == INT_MAX ? -1 : ans);
}
