#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///Sack
///Determine the minimum length of a path that has sum k
struct edge
{
int to;
ll w;
};
vector<edge> adjList[200005];
int Size[200005];
int getSize(int u,int p)
{
Size[u]=1;
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
Size[u]+=getSize(v,u);
}
return Size[u];
}
ll k;
ll minimum=INT_MAX;
map<ll,int>* sack[200005]; //<distance from the root, depth>
typedef pair<ll,int> pii;
void dfs(int u,int p,ll distRoot,int depth)
{
int greatest=0,bigChild=-1;
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
dfs(v,u,distRoot+e.w,depth+1);
if(Size[v]>greatest){
greatest=Size[v];
bigChild=v;
}
}
if(bigChild==-1)
sack[u]=new map<ll,int>;
else
sack[u]=sack[bigChild];
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
if(v==bigChild) continue;
for(pii x: *sack[v]){ //Combine two lines in that subtree
ll dist=x.first-distRoot;
ll complement=k-dist+distRoot;
if(complement>=0 && (*sack[u]).find(complement)!=(*sack[u]).end()){
ll length=(*sack[u])[complement]+x.second;
length-=(ll)2*depth;
minimum=min(minimum,length);
}
}
for(pii x: *sack[v]){ //Copy information from child
if((*sack[u])[x.first]==0) (*sack[u])[x.first]=x.second;
else{
int length=(*sack[u])[x.first];
(*sack[u])[x.first]=min(length,x.second);
}
}
}
if((*sack[u]).find(k+distRoot)!=(*sack[u]).end()){ //Check if a line has sum k
ll length=(*sack[u])[k+distRoot];
length-=depth;
minimum=min(minimum,length);
}
if((*sack[u])[distRoot]==0) (*sack[u])[distRoot]=depth; //Add line from root to u to the sack
else{
int length=(*sack[u])[distRoot];
(*sack[u])[distRoot]=min(length,depth);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0]+1;
int b=H[i][1]+1;
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
getSize(1,0);
dfs(1,0,0,0);
return (minimum!=INT_MAX)? minimum : -1;
}
