#include <bits/stdc++.h>
//#include "race.h"
using namespace std;
#define N 200002
#define INF 1000000020
#define INFLL 1000000000000000020
#define fi first
#define se second
#define pb push_back
#define LOG 18
#define SQRT 25
typedef long int ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;
typedef tuple< int, int, int> tiii;
typedef tuple< ll, ll, ll> tlll;
vector<ll>*vet[N];
ll ans=N;
ll k;
ll sz[N];
ll lvl[N];
ll sum[N];
vector<ll>grafo[N];
map<pll,ll>qtd;
map<pll,ll> :: iterator it;
map<pll,ll>peso;
void ADD(ll val,ll nivel)
{
qtd[{val,nivel}]++;
return;
}
void REMOVE(ll val,ll nivel)
{
qtd[{val,nivel}]--;
if(!qtd[{val,nivel}])
{
qtd.erase({val,nivel});
}
return;
}
void build(ll u,ll p)
{
sz[u]=1;
ll w;
for(auto v : grafo[u])
{
if(v==p)
continue;
w=peso[{u,v}];
lvl[v]=lvl[u]+1LL;
sum[v]=sum[u]+w;
build(v,u);
sz[u]+=sz[v];
}
return;
}
void DFS(ll u,ll p,bool keep)
{
ll mx=-1,big;
for(auto v : grafo[u])
{
if(v==p)
continue;
if(mx<sz[v])
{
mx=sz[v];
big=v;
}
}
for(auto v : grafo[u])
{
if(v==p || v==big)
continue;
DFS(v,u,false);
}
if(mx!=-1)
{
DFS(big,u,true);
vet[u]=vet[big];
}else
{
vet[u]=new vector<ll>();
}
ll K=k+2*sum[u];
(*vet[u]).pb(u);
ADD(sum[u],lvl[u]);
for(auto v : grafo[u])
{
if(v==p || v==big)
continue;
for(auto x : (*vet[v]))
{
it=qtd.lower_bound({K-sum[x],0LL});
if(it!=qtd.end() &&
(*it).first.first==K-sum[x])
ans=min(ans,lvl[x]+
(*it).first.second-
2*lvl[u]);
}
for(auto x : (*vet[v]))
{
(*vet[u]).pb(x);
ADD(sum[x],lvl[x]);
}
}
it=qtd.lower_bound({k+sum[u],0LL});
if(it!=qtd.end() &&
(*it).first.first==k+sum[u])
ans=min(ans,(*it).first.second-lvl[u]);
if(!keep)
{
for(auto x : (*vet[u]))
{
REMOVE(sum[x],lvl[x]);
}
}
return;
}
int best_path(int n, int K, int H[][2], int L[])
{
ll i=0,u,v;
k=K;
while(i<n-1)
{
u=H[i][0];
v=H[i][1];
grafo[u].pb(v);
grafo[v].pb(u);
peso[{u,v}]=peso[{v,u}]=L[i];
i++;
}
lvl[0]=1;
build(0,0);
DFS(0,0,true);
if(ans>=n)
ans=-1;
return ans;
}
