#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned uint;
typedef __int128 bint;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;
template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// mt19937_64 for unsigned long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 2e5 + 5;
int sz[N];
int k, ans;
bool vis[N];
map<int, int> ht;
vector<pair<int, int>> 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] << 1 > n)
return getCentroid(ch, node, n);
}
return node;
}
int query(int node, int par, int dep, int tot)
{
if(tot > k)
return 1e9;
int ret = (ht.find(k - tot) != ht.end() ? dep + ht[k - tot] : 1e9);
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
ret = min(ret, query(ch, node, dep + 1, tot + w));
}
return ret;
}
void update(int node, int par, int dep, int tot)
{
if(tot > k)
return;
if(ht.find(tot) != ht.end())
ht[tot] = min(ht[tot], dep);
else
ht[tot] = dep;
for(auto &[ch, w]: G[node])
{
if(ch == par || vis[ch])
continue;
update(ch, node, dep + 1, tot + w);
}
}
void solveSubTree(int centroid, int par)
{
ht.clear(), ht[0] = 0;
for(auto &[ch, w]: G[centroid])
{
if(ch == par || vis[ch])
continue;
ans = min(ans, query(ch, centroid, 1, w));
update(ch, centroid, 1, w);
}
}
void decompose(int node, int par)
{
dfsSZ(node, par);
int centroid = getCentroid(node, par, sz[node]);
vis[centroid] = true;
solveSubTree(centroid, par);
for(auto &[ch, w]: G[centroid])
{
if(ch == par || vis[ch])
continue;
decompose(ch, centroid);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
for(int i = 0; i < n; i++)
G[i].clear(), vis[i] = 0;
k = K, ans = 1e9;
vector<pair<pair<int, int>, int>> e;
for(int i = 0; i < n - 1; i++)
{
e.push_back({{H[i][0], H[i][1]}, L[i]});
if(L[i] == k)
return 1;
}
for(auto &[p, w]: e)
G[p.first].emplace_back(p.second, w), G[p.second].emplace_back(p.first, w);
decompose(0, -1);
return (ans == 1e9 ? -1 : ans);
}
//void doWork()
//{
// 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);
//}
//
//signed main()
//{
// FIO
// int T = 1;
//// cin >> T;
// for(int i = 1; i <= T; i++)
// doWork();
//}
/*
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
*/
