#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6;
bool vis[N];
int sz[N], k;
int ans = -1;
map<ll, int> mn;
vector<pair<int, ll>> G[N];
int dfsSZ(int node, int par = -1)
{
sz[node] = 1;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[node])
continue;
sz[node] += dfsSZ(ch, node);
}
return sz[node];
}
int getCentroid(int node, int par, int n)
{
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
if(sz[ch] * 2 > n)
return getCentroid(ch, node, n);
}
return node;
}
void dfs(int node, int par = -1, ll dist = 0, int dep = 0)
{
if(mn.find(k - dist) != mn.end())
ans = (ans == -1 ? mn[k - dist] + dep : min(ans, mn[k - dist] + dep));
if(mn.find(dist) != mn.end())
mn[dist] = min(mn[dist], dep);
else
mn[dist] = dep;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
dfs(ch, node, dist + w, dep + 1);
}
}
void decompose(int node = 0)
{
int centroid = getCentroid(node, -1, dfsSZ(node));
mn.clear();
dfs(centroid);
vis[centroid] = true;
for(auto &[ch, w]: G[centroid])
{
if(vis[ch])
continue;
decompose(ch);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k = K, ans = -1;
mn.clear();
for(int i = 0; i <= n; i++)
G[i].clear(), vis[i] = false;
for(int i = 0; i < n - 1; i++)
{
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
decompose();
return ans;
}
//
//int main()
//{
// int n, K;
// cin >> n >> K;
// int H[n][2], L[n];
// for(int i = 0; i < n - 1; i++)
// cin >> H[i][0] >> H[i][1];
// for(int i = 0; i < n - 1; i++)
// cin >> L[i];
//
// cout << best_path(n, K, H, L);
//}
/*
4 3
0 1
1 2
1 3
1 2 4
3 3
0 1
1 2
1 1
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
*/
