#include <bits/stdc++.h>
#include "race.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,k,ans=1e9,dist[200005],niv[200005],nr[200005],par[200005];
vector<int> vals;
vector<vector<pii>> allvals;
int mini[1000005],m1[1000005],m2[1000005];
struct date
{
ll a,b,cost;
} G[200005];
bool edgeuse[200005];
vector<int> muchii[200005];
void build(int nod)
{
nr[nod]=1;
for(int i:muchii[nod])
{
int a=G[i].a,b=G[i].b;
int x=(a^b^nod);
if(!edgeuse[i]&&x!=par[nod])
{
par[x]=nod;
build(x);
nr[nod]+=nr[x];
}
}
}
void reroot(int nod,int fiu)
{
nr[nod]-=nr[fiu];
nr[fiu]+=nr[nod];
par[fiu]=0;
par[nod]=fiu;
}
int findcentroid(int nod)
{
par[nod]=0;
build(nod);
bool found=0;
while(!found)
{
found=1;
for(int i:muchii[nod])
if(!edgeuse[i])
{
int a=G[i].a,b=G[i].b;
int x=(a^b^nod);
if(nr[x]>nr[nod]/2)
{
reroot(nod,x);
nod=x;
found=0;
break;
}
}
}
return nod;
}
void dfs(int nod)
{
if(dist[nod]==k)
ans=min(ans,niv[nod]);
for(int i:muchii[nod])
if(!edgeuse[i])
{
int a=G[i].a,b=G[i].b;
int x=(a^b^nod);
if(x!=par[nod])
{
par[x]=nod;
niv[x]=niv[nod]+1;
dist[x]=dist[nod]+G[i].cost;
dfs(x);
}
}
}
void dfs1(int nod)
{
if(dist[nod]<k&&dist[nod]>0)
{
vals.push_back(dist[nod]);
mini[dist[nod]]=min(1LL*mini[dist[nod]],niv[nod]);
}
for(int i:muchii[nod])
if(!edgeuse[i])
{
int a=G[i].a,b=G[i].b;
int x=(a^b^nod);
if(par[nod]!=x)
dfs1(x);
}
}
void go(int nod)
{
int root=findcentroid(nod);
dist[root]=0;
niv[root]=0;
par[root]=0;
dfs(root);
allvals.clear();
for(int i:muchii[root])
if(!edgeuse[i])
{
vals.clear();
int a=G[i].a,b=G[i].b;
int x=(a^b^root);
dfs1(x);
sort(vals.begin(),vals.end());
vals.erase(unique(vals.begin(),vals.end()),vals.end());
vector<pii> mine;
for(int j:vals)
{
if(mini[j]<m1[j])
{
m2[j]=m1[j];
m1[j]=mini[j];
}
else if(mini[j]<m2[j])
m2[j]=mini[j];
mine.push_back({j,mini[j]});
mini[j]=1e9;
}
allvals.push_back(mine);
}
for(auto v:allvals)
{
for(pii a:v)
mini[a.first]=a.second;
for(pii a:v)
{
int need=k-a.first;
if(need==0||need==k)
continue;
ll val=a.second;
if(m1[need]==mini[need])
val+=m2[need];
else
val+=m1[need];
ans=min(ans,val);
}
for(pii a:v)
mini[a.first]=1e9;
}
for(auto v:allvals)
{
for(pii a:v)
m1[a.first]=m2[a.first]=1e9;
}
for(int i:muchii[root])
if(!edgeuse[i])
{
edgeuse[i]=1;
int a=G[i].a,b=G[i].b;
int x=(a^b^root);
go(x);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for(int i=1;i<=k;i++)
{
m1[i]=m2[i]=1e9;
mini[i]=1e9;
}
for(int i=0;i<n-1;i++)
{
int a=H[i][0];
int b=H[i][1];
a++;
b++;
G[i+1]={a,b,0};
muchii[a].push_back(i+1);
muchii[b].push_back(i+1);
}
for(int i=0;i<n-1;i++)
G[i+1].cost=L[i];
go(1);
if(ans<=n)
return ans;
return -1;
}
