#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, K = 1e6 + 10, INF = 1e9;
bool ch[K];
vector<int> adj[N], len[N], upd;
int h[N], longueur, mini = INF, minAut[K];
void getMin(int i, int pre, int dist, int nbAut) {
if(h[i] != -1 || dist > longueur)
return;
mini = min(mini, nbAut + minAut[longueur - dist]);
nbAut++;
int t = adj[i].size();
for(int j = 0; j < t; j++)
if(adj[i][j] != pre)
getMin(adj[i][j], i, dist + len[i][j], nbAut);
}
void update(int i, int pre, int dist, int nbAut) {
if(h[i] != -1 || dist > longueur)
return;
if(!ch[dist]) {
ch[dist] = true;
upd.push_back(dist);
}
minAut[dist] = min(minAut[dist], nbAut);
nbAut++;
int t = adj[i].size();
for(int j = 0; j < t; j++)
if(adj[i][j] != pre)
update(adj[i][j], i, dist + len[i][j], nbAut);
}
int centroid(int i, int pre, int sz, int id) {
if(h[i] != -1)
return 0;
//cout << "CALL " << i << ' ' << sz << ' ' << id << '\n';
int t = adj[i].size(), s[t], sum = 1, v = -1;
for(int j = 0; j < t; j++)
if(adj[i][j] == pre) {
v = j;
} else {
s[j] = centroid(adj[i][j], i, sz, id);
sum += s[j];
}
if(v != -1)
s[v] = sz - sum;
int maxi = 0;
for(int j = 0; j < t; j++)
maxi = max(maxi, s[j]);
//cout << "TEST " << i << ' ' << h[i] << ' ' << maxi << ' ' << (sz+1)/2 << ' ' << sz << '\n';
if(h[i] == -1 && maxi <= sz/2) {
h[i] = id;
minAut[0] = 0;
upd.push_back(0);
for(int j = 0; j < t; j++) {
getMin(adj[i][j], i, len[i][j], 1);
update(adj[i][j], i, len[i][j], 1);
}
for(int j : upd) {
ch[j] = false;
minAut[j] = INF;
}
upd.clear();
//cout << i << ' ' << h[i] << ' ' << t << '\n';
id++;
/*for(int j = 0; j < t; j++)
cout << ' ' << adj[i][j] << ' ' << s[j] << '\n';*/
for(int j = 0; j < t; j++)
centroid(adj[i][j], i, s[j], id);
}
return sum;
}
int best_path(int n, int k, int H[][2], int L[]) {
longueur = k;
for(int i = 0; i < K; i++)
minAut[i] = INF;
for(int i = 0; i < n; i++)
h[i] = -1;
for(int i = 0; i < n-1; i++) {
len[H[i][0]].push_back(L[i]);
len[H[i][1]].push_back(L[i]);
adj[H[i][0]].push_back(H[i][1]);
adj[H[i][1]].push_back(H[i][0]);
}
centroid(0, -1, n, 0);
if(mini == INF)
return -1;
return mini;
}
