#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
#define fr first
#define sc second
const int N = 200000;
int k, sz[N + 5], addlg[N + 5], addnr[N + 5], ans = 1e9;
vector<pii> vec[N + 5];
map<int, pii> mp[N + 5];
void dfs(int nod, int papa)
{
int fmax = 0, lg;
sz[nod] = 1;
for(auto [i, j] : vec[nod])
{
if(i == papa)
continue;
dfs(i, nod);
sz[nod] += sz[i];
if(sz[fmax] < sz[i])
fmax = i, lg = j;
}
if(fmax == 0)
{
mp[nod][0] = {0, 1};
return;
}
swap(mp[nod], mp[fmax]);
swap(addlg[nod], addlg[fmax]);
swap(addnr[nod], addnr[fmax]);
addlg[nod] += lg;
addnr[nod] ++;
for(auto [i, j] : vec[nod])
{
if(i == papa)
continue;
if(i == fmax)
continue;
addlg[i] += j;
addnr[i] += 1;
for(auto l : mp[i])
if(l.sc.sc == 1)
{
if(mp[nod][k - addlg[nod] - addlg[i] - l.fr].sc == 1)
ans = min(ans, l.sc.fr + addnr[nod] + addnr[i] + mp[nod][k - addlg[nod] - addlg[i] - l.fr].fr);
}
for(auto l : mp[i])
if(l.sc.sc == 1)
{
if(mp[nod][l.fr + addlg[i] - addlg[nod]].sc == 1)
mp[nod][l.fr + addlg[i] - addlg[nod]] = {min(mp[nod][l.fr + addlg[i] - addlg[nod]].fr, l.sc.fr + addnr[i] - addnr[nod]), 1};
else
mp[nod][l.fr + addlg[i] - addlg[nod]] = {l.sc.fr + addnr[i] - addnr[nod], 1};
}
}
if(mp[nod][k - addlg[nod]].sc == 1)
ans = min(ans, mp[nod][k - addlg[nod]].fr + addnr[nod]);
mp[nod][-addlg[nod]] = {-addnr[nod], 1};
/*cout << nod << " " << addlg[nod] << " " << addnr[nod] << '\n';
for(auto i : mp[nod])
if(i.sc.sc == 1)
cout << i.fr << " " << i.sc.fr << '\n';*/
}
signed best_path(signed n, signed K, signed h[][2], signed l[])
{
k = K;
if(k == 0)
return 0;
for(int i = 0; i < n - 1; i ++)
{
vec[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
vec[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
}
dfs(1, 0);
if(ans == 1e9)
return -1;
return ans;
}
