#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
int best_path(int N, int K, int H[][2], int L[]) {
vector<vi> adj; adj.resize(N);
vector<vii> adjW; adjW.resize(N);
vector<bool> ignore; ignore.assign(N,0);
vi sz; sz.assign(N,0);
map<int,vii> mp;
int ans = N+1;
RE(i,N-1) RE(j,2) adj[H[i][j]].push_back(H[i][!j]);
RE(i,N-1) RE(j,2) adjW[H[i][j]].push_back({H[i][!j], L[i]});
std::function<void(int,int)> dfsSize;
std::function<int(int,int,int)> dfsCentroid;
std::function<void(int,int,int,int,int)> dfsMap;
std::function<void(int)> centroidDecomp;
dfsSize = [&](int u, int p) {
sz[u] = 1;
FOR(v,adj[u]) {
if(ignore[v]) continue;
if(v == p) continue;
dfsSize(v,u);
sz[u] += sz[v];
}
};
dfsCentroid = [&](int u, int p, int maxSize) {
FOR(v,adj[u]) {
if(ignore[v]) continue;
if(v == p) continue;
if(sz[v] > maxSize) return dfsCentroid(v,u,maxSize);
}
return u;
};
dfsMap = [&](int u, int p, int root, int len, int depth) {
mp[depth].push_back({len,root});
FOR(v,adjW[u]) {
if(ignore[v.fi]) continue;
if(v.fi == p) continue;
dfsMap(v.fi,u,root,len+1,depth+v.se);
}
};
auto findCentroid = [&](int u) {
dfsSize(u,-1);
return dfsCentroid(u,-1,sz[u]/2);
};
centroidDecomp = [&](int u) {
int cent = findCentroid(u);
mp.clear();
FOR(v,adjW[cent]) {
if(ignore[v.fi]) continue;
dfsMap(v.fi,cent,v.fi,1,v.se);
}
mp[0].push_back({-1,0});
FOR(p,mp) {
sort(all(p.se));
p.se.erase(unique(all(p.se)), p.se.end());
if(p.se.size() > 2)
p.se.resize(2);
}
FOR(p,mp) {
auto& f1 = p.se;
auto& f2 = mp[K - p.fi];
FOR(i,f1) FOR(j,f2) if(i.se != j.se) ans = min(ans, i.fi + j.fi);
}
// recursive
ignore[cent] = 1;
FOR(v,adj[cent]) {
if(ignore[v]) continue;
centroidDecomp(v);
}
};
centroidDecomp(0);
if(ans == N+1) ans = -1;
return ans;
}
