#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
int ANS;
int K;
struct node{
set<pair<int, int>> e;
map<int, int> m;
int c = 0;
};
vector<node> g;
int cdfs(int start, int par, int tot){
for(auto nex: g[start].e){
if (nex.first != par and g[nex.first].c > tot/2){
return cdfs(nex.first, start, tot);
}
}
return start;
}
int countdfs(int start, int par){
g[start].c = 1;
for(auto nex: g[start].e){
if (nex.first != par){
g[start].c += countdfs(nex.first, start);
}
}
return g[start].c;
}
int centralise(int start){
// cout << "Finding centre of " << start << "\n";
countdfs(start, - 1);
return cdfs(start, -1, g[start].c);
}
void dfs2(int start, int par, int root, int length, int depth){
if (g[root].m.count(K - length) != 0){
ANS = min(ANS, depth + g[root].m[K - length]);
// if (depth + g[root].m[K - length] == 1){
// cout << start << " " << root << " " << depth << "\n";
// }
}
for(auto nex: g[start].e){
if (nex.first != par){
dfs2(nex.first, start, root, length + nex.second, depth + 1);
}
}
}
void dfs1(int start, int par, int root, int length, int depth){
if (g[root].m.count(length) == 0){
g[root].m[length] = depth;
}
// cout << "adding " << length << " " << depth << " " << root << "\n";
g[root].m[length] = min(g[root].m[length],depth);
// cout << "g[root].m[length] = " << g[root].m[length] << "\n";
for(auto nex: g[start].e){
if (nex.first != par){
dfs1(nex.first, start, root, length + nex.second, depth + 1);
}
}
}
void process(int start){
g[start].m[0] = 0;
//assumes start is a centroid
// cout << "processing: " << start << "\n";
vector<int> do_later;
for(auto edge: g[start].e){
g[edge.first].e.erase({start, edge.second});
dfs2(edge.first, start, start, edge.second, 1);
dfs1(edge.first, start, start, edge.second, 1);
// cout << "ANS = " << ANS << "\n";
// cout << "Looking into " << edge.first << "\n";
process(centralise(edge.first));
}
// cout << "Finished: " << start << "\n";
}
int best_path(int N, int k, int H[][2], int L[]){
g.resize(N);
K = k;
ANS = N+1;
FOR(i, 0, N - 1){
g[H[i][0]].e.insert({H[i][1], L[i]});
g[H[i][1]].e.insert({H[i][0], L[i]});
}
process(centralise(0));
if (ANS == N + 1){
ANS = -1;
}
return ANS;
}
