#include "race.h"
#include<vector>
#include<algorithm>
#define DIM 200005
#define f first
#define s second
using namespace std;
int viz[DIM], num[DIM], d[1000005];
vector< pair<int, int> > v[DIM];
struct str{
int nod, d, dist, tf;
};
vector<str> w[DIM];
void dfs1(int nod, int t){
num[nod] = 1;
for(int i = 0; i < v[nod].size(); i++){
int vecin = v[nod][i].f;
if(vecin != t && viz[vecin] == 0){
dfs1(vecin, nod);
num[nod] += num[vecin];
}
}
}
int findcen(int nod, int t, int k){
for(int i = 0; i < v[nod].size(); i++){
int vecin = v[nod][i].f;
if(vecin != t && viz[vecin] == 0){
if(num[vecin] > k / 2){
return findcen(vecin, nod, k);
}
}
}
return nod;
}
void dfs(int nod, int t, int cen, int d, int dist, int fiu){
w[cen].push_back( {nod, d, dist, fiu} );
for(int i = 0; i < v[nod].size(); i++){
int vecin = v[nod][i].f;
if(vecin != t && viz[vecin] == 0){
int ndist = min(10000000, dist + v[nod][i].s);
dfs(vecin, nod, cen, d + 1, ndist, fiu);
}
}
}
void decomp(int nod){
int x, i, vecin;
dfs1(nod, -1);
x = findcen(nod, -1, num[nod]);
viz[x] = 1;
for(i = 0; i < v[x].size(); i++){
vecin = v[x][i].f;
if(viz[vecin] == 0){
dfs(vecin, x, x, 1, v[x][i].s, vecin);
}
}
for(i = 0; i < v[x].size(); i++){
vecin = v[x][i].f;
if(viz[vecin] == 0){
decomp(vecin);
}
}
}
int best_path(int n, int k, int h[][2], int lg[]){
int i, j, x, y, sol, ii;
for(i = 0; i < n - 1; i++){
x = h[i][0];
y = h[i][1];
v[x].push_back( make_pair(y, lg[i]) );
v[y].push_back( make_pair(x, lg[i]) );
}
decomp(0);
for(i = 1; i <= k; i++){
d[i] = n;
}
sol = n;
for(i = 0; i < n; i++){
d[0] = 0;
for(j = 0; j < w[i].size(); j++){
for(ii = j; ii < w[i].size(); ii++){
if(w[i][j].tf != w[i][ii].tf){
break;
}
if(w[i][ii].dist <= k){
sol = min(sol, w[i][ii].d + d[ k - w[i][ii].dist ]);
}
}
for(ii = j; ii < w[i].size(); ii++){
if(w[i][j].tf != w[i][ii].tf){
break;
}
if(w[i][ii].dist <= k){
d[ w[i][ii].dist ] = min(d[ w[i][ii].dist ], w[i][ii].d);
}
}
j = ii - 1;
}
for(j = 0; j < w[i].size(); j++){
if(w[i][j].dist <= k){
d[ w[i][j].dist ] = n;
}
}
}
if(sol == n){
return -1;
}
return sol;
}
