#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<pair<int,int>> adj[200005];
int minDist[1000005];
int sizeSubTree[200005];
bool used[200005];
int ans;
vector<int> touched;
void dfsSize(int u, int p)
{
sizeSubTree[u] = 1;
for (int i = 0; i < (int) adj[u].size(); i++)
{
int v = adj[u][i].first;
if (v == p || used[v])
{
continue;
}
dfsSize(v, u);
sizeSubTree[u] += sizeSubTree[v];
}
}
int findCentroid(int u, int p, int total)
{
for (int i = 0; i < (int) adj[u].size(); i++)
{
int v = adj[u][i].first;
if (v == p || used[v])
{
continue;
}
if (2 * sizeSubTree[v] > total)
{
return findCentroid(v, u, total);
}
}
return u;
}
void dfs(int u, int p, int edges, int dist, bool writeMode)
{
if (dist > k)
{
return;
}
if (!writeMode)
{
int need = k - dist;
if (need >= 0 && minDist[need] < n + 5)
{
ans = min(ans, edges + minDist[need]);
}
}
else
{
if (minDist[dist] > edges)
{
if (minDist[dist] == n + 5)
{
touched.push_back(dist);
}
minDist[dist] = edges;
}
}
for (int i = 0; i < (int) adj[u].size(); i++)
{
int v = adj[u][i].first;
int w = adj[u][i].second;
if (v == p || used[v])
{
continue;
}
dfs(v, u, edges + 1, dist + w, writeMode);
}
}
void decompose(int u)
{
dfsSize(u, -1);
int c = findCentroid(u, -1, sizeSubTree[u]);
used[c] = true;
minDist[0] = 0;
touched.push_back(0);
for (int i = 0; i < (int) adj[c].size(); i++)
{
int v = adj[c][i].first;
int w = adj[c][i].second;
if (used[v])
{
continue;
}
dfs(v, c, 1, w, false);
dfs(v, c, 1, w, true);
}
for (int d : touched)
{
minDist[d] = n + 5;
}
touched.clear();
for (int i = 0; i < (int) adj[c].size(); i++)
{
int v = adj[c][i].first;
if (!used[v])
{
decompose(v);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (int i = 0; i < n; i++)
{
adj[i].clear();
used[i] = false;
}
for (int i = 0; i <= k; i++)
{
minDist[i] = n + 5;
}
for (int i = 0; i < n - 1; i++)
{
int u = H[i][0];
int v = H[i][1];
int w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
ans = n + 5;
decompose(0);
return (ans == n + 5 ? -1 : ans);
}
