#include <bits/stdc++.h>
using namespace std;
int ans = INT_MAX;
using ll = long long;
vector<vector<pair<int, ll>>> adj;
vector<int> best, ct, subtree_size, centroids;
int flag = 0;
int k;
// ideia
// consultar complementos procurando pares que somem K
void dfs1(int u, int p, int edges, ll w)
{
if (w > k) // poda: soma > K não nos interessa
return;
int goal = k - w;
int value = INT_MAX;
if (ct[goal] == flag)
value = best[goal];
if (value != INT_MAX)
ans = min(ans, value + edges);
for (auto &pr : adj[u])
{
int v = pr.first;
int weight = pr.second;
if (v != p)
dfs1(v, u, edges + 1, w + weight);
}
}
// dfs2
// ideia: atualiza "best" com as distâncias desta subárvore
void dfs2(int at, int prev, int edges, ll w)
{
if (w > k)
return;
if (w >= 0 && w <= k) {
if (ct[w] == flag)
{
best[w] = min(best[w], edges);
}
else
{
best[w] = edges;
ct[w] = flag;
}
}
for (auto &pr : adj[at])
{
int to = pr.first;
int weight = pr.second;
if (to == prev)
continue;
dfs2(to, at, edges + 1, weight + w);
}
}
void subtree_sz(int at, int prev)
{
subtree_size[at] = 1;
for (auto &pr : adj[at])
{
int to = pr.first;
int w = pr.second;
if (to == prev) continue;
subtree_sz(to, at);
subtree_size[at] += subtree_size[to];
}
}
int find_centroid(int at, int prev, int n)
{
for (auto &pr : adj[at])
{
int to = pr.first;
int w = pr.second;
if (to == prev) continue;
if (subtree_size[to] > n / 2)
return find_centroid(to, at, n);
}
return at;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
adj.assign(N, {});
best.assign(K + 1, INT_MAX);
ct.assign(K + 1, -1);
subtree_size.assign(N, 0);
centroids.assign(N, 0);
flag = 0;
ans = INT_MAX;
for (int i = 0; i < N - 1; i++)
{
int a = H[i][0];
int b = H[i][1];
int w = L[i];
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
queue<int> q;
q.push(0);
while (!q.empty())
{
int at = q.front();
q.pop();
subtree_sz(at, -1);
int centroid = find_centroid(at, -1, subtree_size[at]);
best[0] = 0;
ct[0] = flag;
centroids[centroid] = 1;
for (auto &pr : adj[centroid])
{
int to = pr.first;
ll w = pr.second;
if (!centroids[to])
{
dfs1(to, centroid, 1, w);
dfs2(to, centroid, 1, w);
q.push(to);
}
}
flag++;
}
return (ans == INT_MAX) ? -1 : ans;
}
