#include "race.h"
#include <vector>
#include <iostream>
#include <set>
#include <cstdlib>
using namespace std;
const int maxN = 200'000;
int N;
long long K;
vector<int> edge[1+maxN+1];
vector<long long> dist[1+maxN+1];
int ans = maxN;
vector<int> parent(1+maxN+1, maxN);
vector<int> subtree(1+maxN+1, 1);
int curr_size = 0;
vector<int> inaccessible(1+maxN+1, 0);
void dfs(int u, int p, int b)
{
// cerr << "normal dfs " << u << ' ' << p << ' ' << b << '\n';
curr_size++;
parent[u] = p;
subtree[u] = 1;
for(int v: edge[u])
{
if(inaccessible[v]) continue;
if(v == p || v == b) continue;
dfs(v, u, b);
subtree[u] += subtree[v];
}
}
int getSize(int u, int v)
{
if(parent[v] == u) return subtree[v];
else return curr_size - subtree[u];
}
vector< pair<long long, int> > dist_list[1+maxN+1];
int error_ct = 0;
void dfs2(int u, int p, int r, int b, long long d, int e) //parent, root, banned
{
// error_ct++;
// if(error_ct == 100) exit(0);
// cerr << "dfs2 " << u << ' ' << p << ' ' << r << ' ' << b << ' ' << d << ' ' << e << '\n';
dist_list[r].push_back(make_pair(d, e));
for(int z = 0; z < int(edge[u].size()); z++)
{
int v = edge[u][z];
long long w = dist[u][z];
if(v == p || v == b) continue;
if(inaccessible[v]) continue;
dfs2(v, u, r, b, d+w, e+1);
}
}
multiset< pair<long long, int> > X;
void solve(int u, int p)
{
// cerr << "\n\n\n\n\n";
// cerr << "solve " << u << ' ' << p << '\n';
curr_size = 0;
dfs(u, p, p);
int c = u;
while(1)
{
bool flag = 0;
for(int v: edge[c])
{
if(inaccessible[v]) continue;
if(v == p) continue;
if(2*getSize(c, v) > curr_size)
{
c = v;
flag = 1;
break;
}
}
if(!flag) break;
}
// cerr << "c = " << c << '\n';
inaccessible[c]++;
// cerr << "don't access " << c << '\n';
X.clear();
for(int e = 0; e < int(edge[c].size()); e++)
{
int v = edge[c][e];
long long w = dist[c][e];
if(v == p) continue;
if(inaccessible[v]) continue;
dist_list[v].clear();
dfs2(v, c, v, p, w, 1);
for(auto x: dist_list[v]) X.insert(x);
// cerr << c << " -> " << v << ": ";
// for(auto x: dist_list[v]) cerr << x.first <<","<<x.second << " | ";
// cerr << '\n';
}
auto y1 = X.lower_bound(make_pair(K, -1));
if(y1 != X.end() && y1->first == K) ans = min(ans, y1->second);
for(int e = 0; e < int(edge[c].size()); e++)
{
int v = edge[c][e];
long long w = dist[c][e];
if(v == p) continue;
if(inaccessible[v]) continue;
for(auto x: dist_list[v]) X.erase(X.find(x));
for(auto x: dist_list[v])
{
auto y = X.lower_bound(make_pair(K - x.first, -1));
if(y == X.end()) continue;
if(y->first + x.first != K) continue;
ans = min(ans, y->second + x.second);
}
for(auto x: dist_list[v]) X.insert(x);
}
for(int v: edge[c])
{
if(v == p) continue;
if(inaccessible[v]) continue;
solve(v, c);
}
inaccessible[c]--;
// cerr << "do access " << c << '\n';
}
int best_path(int N_, int K_, int H_[][2], int L_[])
{
N = N_;
K = K_;
for(int e = 0; e < N-1; e++)
{
edge[H_[e][0]].push_back(H_[e][1]);
dist[H_[e][0]].push_back(L_[e]);
edge[H_[e][1]].push_back(H_[e][0]);
dist[H_[e][1]].push_back(L_[e]);
}
solve(0, maxN); //solve for paths belonging to centroid subtree of u
if(ans == maxN) ans = -1;
return ans;
}
