#include <bits/stdc++.h>
#include "race.h"
#include <vector>
#define maxn 2000005
#define mod 1000000007
#define INF 1000000005
#define X first
#define Y second
using namespace std;
vector <pair <int, int>> v[maxn];
int sz[maxn];
int used[maxn];
int find_sz(int node, int parent)
{
sz[node] = 1;
for(pair <int, int> e : v[node])
{
if(e.X == parent || used[e.X] == true)
continue;
sz[node] += find_sz(e.X , node);
}
return sz[node];
}
int find_centroid(int node, int parent, int _sz)
{
for(pair <int, int> e : v[node])
{
if(e.X == parent || used[e.X] == true)
continue;
if(sz[e.X] * 2 > _sz)
return find_centroid(e.X, node, _sz);
}
return node;
}
int c = 1e8;
int ans = INF;
int help[maxn];
void dfs1(int node, int parent, int depth, int weight, int k)
{
if(weight > 0 && weight <= k)
help[weight] = 1e8;
if(k > weight)
help[k - weight] = 1e8;
for(pair <int, int> e : v[node])
{
if(e.X == parent || used[e.X] == true)
continue;
dfs1(e.X, node, depth + 1, weight + e.Y, k);
}
}
void dfs2(int node, int parent, int depth, int weight, int k)
{
if(weight <= k && parent != -1)
ans = min(ans, help[k - weight] + depth);
for(pair <int, int> e : v[node])
{
if(e.X == parent || used[e.X] == true)
continue;
dfs2(e.X, node, depth + 1, weight + e.Y, k);
}
}
void dfs3(int node, int parent, int depth, int weight, int k)
{
if (k >= weight && parent != -1)
help[weight] = min(help[weight], depth);
for (pair <int, int> e : v[node])
{
if (e.X == parent || used[e.X])
continue;
dfs3(e.X, node, depth + 1, weight + e.Y , k);
}
}
void decompose(int node , int k)
{
int cur_sz = find_sz(node , -1);
int centroid = find_centroid(node , -1 , cur_sz);
used[centroid] = true;
for(pair <int , int> e : v[centroid])
{
if(used[e.X] == true)
continue;
dfs1(e.X , centroid , 1 , e.Y , k);
}
for(pair <int , int> e : v[centroid])
{
if(used[e.X] == true)
continue;
dfs2(e.X, centroid , 1 , e.Y , k);
dfs3(e.X , centroid , 1 , e.Y , k);
}
for(pair <int , int> e : v[centroid])
{
if(used[e.X] == true)
continue;
decompose(e.X , k);
}
}
int best_path(int n , int k , int h[][2] , int l[])
{
for(int i = 0; i < n - 1; i++)
{
v[h[i][0]].push_back({h[i][1] , l[i]});
v[h[i][1]].push_back({h[i][0] , l[i]});
}
help[0] = 0;
decompose(0 , k);
if(ans > n)
return -1;
return ans;
}
