#include <iostream>
#include <vector>
#include <map>
#define NMAX 200000
#define INF 1000000000000000000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <pair <int, int>> graph[NMAX + 10];
map <long long, long long> mp;
int ok, mark[NMAX + 10], sz[NMAX + 10];
long long k, ans = INF;
void solve(int node, int parent, long long depth, long long cost)
{
if (cost > k)
return;
if (ok == 1)
{
if (mp[cost] == 0)
mp[cost] = depth;
else
mp[cost] = min(mp[cost], depth);
}
else
{
if (mp[k - cost] != 0)
ans = min(ans, depth + mp[k - cost] - 2);
}
for (auto it: graph[node])
if (it.first != parent && mark[it.first] == 0)
solve(it.first, node, depth + 1, cost + it.second);
}
int findCentroid(int node, int s, int parent)
{
for (auto it: graph[node])
if (it.first != parent && mark[it.first] == 0 && sz[it.first] * 2 > s)
return findCentroid(it.first, s, node);
return node;
}
int dfs(int node, int parent)
{
sz[node] = 1;
for (auto it: graph[node])
if (it.first != parent && mark[it.first] == 0)
sz[node] = sz[node] + dfs(it.first, node);
return sz[node];
}
void centroid(int node)
{
int aux = dfs(node, -1), cent = findCentroid(node, aux, -1);
mp.clear();
mp[0] = 1;
mark[cent] = 1;
for (auto it: graph[cent])
if (mark[it.first] == 0)
{
ok = 0;
solve(it.first, -1, 2, it.second);
ok = 1;
solve(it.first, -1, 2, it.second);
}
for (auto it: graph[cent])
if (mark[it.first] == 0)
centroid(it.first);
}
int best_path(int N, int K, int H[][2],int L[])
{
k = K;
for (int i = 0; i < N - 1; i++)
{
graph[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
graph[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
}
centroid(1);
if (ans == INF)
return -1;
else
return ans;
}
