#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"race.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;
vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
vector <pii> mp[1000001];
void getsize(int node, int p){
sz[node] = 1;
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
getsize(x.first, node);
sz[node] += sz[x.first];
}
total = sz[node];
}
int centroid(int node, int p){
for(auto x : v[node]){
if(viz[x.first] || x.first == p){
continue;
}
if(sz[x.first] > total / 2)
return centroid(x.first, node);
}
return node;
}
int OneCentroid(int node){
getsize(node, 0);
return centroid(node, 0);
}
void ComputeDist(int node, int p, int subTree, int dist, int level){
d[node] = dist;
pii act = {level, subTree};
if(dist <= k && (!mp[dist].size() || mp[dist].back().first >= level))
mp[dist].push_back(act);
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
}
}
void SuperErase(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k){
mp[dist].clear();
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
SuperErase(x.first, node, subTree, level + 1);
}
}
void Erase(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (mp[dist].size() && mp[dist].back() == act))
mp[dist].pop_back();
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Erase(x.first, node, subTree, level + 1);
}
}
void Add(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (!mp[dist].size() ||mp[dist].back().first >= level))
mp[dist].push_back(act);
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Add(x.first, node, subTree, level + 1);
}
}
void Compute(int node, int p, int level){
int trb = k - d[node];
if(trb >= 0 && mp[trb].size() != 0)
{
int b = mp[trb].back().first;
best = min(best, b + level);
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Compute(x.first, node, level + 1);
}
}
void CD(int node){
int c = OneCentroid(node);
viz[c] = 1;
mp[0].push_back({0, 0});
for(auto x : v[c]){
if(viz[x.first])
continue;
ComputeDist(x.first, c, x.first, x.second, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
Erase(x.first, c, x.first, 1);
Compute(x.first, 0, 1);
Add(x.first, c, x.first, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
SuperErase(x.first, c, x.first, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
CD(x.first);
}
}
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;
v[a].push_back({b, L[i]});
v[b].push_back({a, L[i]});
}
for(int i = 0; i <= k; i++)
mp[i].clear();
CD(1);
if(best == 2e9)
best = -1;
return best;
}
