//https://pastebin.com/jVURaNCJ
#include<bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define N 200005
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
vector<int>gr[N];
gp_hash_table<int, gp_hash_table<int, int>> edge;
//map<int, map<int, int>>edge;
gp_hash_table<int , int>m[N];
int depth[N];
int fin_ans = mod;
int val[N];
int k;
int dfs1(int node, int par)
{
int ans = 0;
for (auto child : gr[node])
{
if (child != par)
{
ans = max(ans, dfs1(child, node) + 1);
}
}
return depth[node] = ans;
}
int dfs(int node, int par)
{
int sz = 0;
int ind;
int not_child = 1;
for (auto child : gr[node])
{
if (child != par )
{
not_child = 0;
int temp = dfs(child, node);
if (temp > sz)
{
sz = temp;
ind = child;
}
}
}
if (not_child == 1) {
val[node] = 0;
return 0;
}
for (auto child : gr[node])
{
if (child == par)
continue;
int to_find = k - edge[node][child];
if (to_find == 0)
fin_ans = 1;
to_find = to_find - val[child];
if (m[child].find(to_find) != m[child].end())
{
fin_ans = min(fin_ans, 1 + depth[child] - m[child][to_find]);
}
}
m[node].swap(m[ind]);
val[node] = val[ind] + edge[node][ind];
m[node][edge[node][ind] - val[node]] = depth[node] - 1;
////////////////////////////////alll deal with child to node
// and inserted bigger_child and done with that
for (auto child : gr[node])
{
if (child != par && child != ind)
{
for (auto i : m[child])
{
int num = i.ff + val[child] + edge[node][child];
int to_find = k - num - val[node];
if (m[node].find(to_find) != m[node].end())
{
fin_ans = min(fin_ans, depth[node] - m[node][to_find] + depth[child] - i.ss + 1);
}
}
int findd = k - edge[node][child] - val[node];
if (m[node].find(findd) != m[node].end())
{
fin_ans = min(fin_ans, depth[node] - m[node][findd] + 1);
}
for (auto i : m[child])
{
int num = i.ff + val[child];
if (num > k)
continue;
int to_insert = num - val[node];
int newd = depth[node] - 1 - (depth[child] - i.ss);
if (m[node].find(to_insert) != m[node].end())
{
if (m[node][to_insert] < newd)
m[node][to_insert] = newd;
}
else
m[node][to_insert] = newd;
}
m[node][edge[node][child] - val[node]] = depth[node] - 1;
}
}
return m[node].size();
}
int best_path(int n, int K, int H[][2], int L[]) {
int i, a, b, c;
k = K;
for (int i = 0; i <= n; i++)
{
gr[i].clear();
m[i].clear();
depth[i] = 0;
val[i] = 0;
}
fin_ans = mod;
edge.clear();
for (i = 0; i < n - 1; i++) {
a = H[i][0]; b = H[i][1]; c = L[i];
a++; b++;
edge[a][b] = c;
edge[b][a] = c;
gr[a].pb(b);
gr[b].pb(a);
}
dfs1(1, 0);
dfs(1, 0);
if (fin_ans == mod)
return -1;
return fin_ans;
}
