#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int NMAX = 2e5;
const int LOGMAX = 20;
const int INF = 1e9;
int totalSize;
vector<pair<int, int>> edges[NMAX];
vector<pair<long long, int>> distCentroidSubtree[NMAX];
int sz[NMAX];
int centroidParent[NMAX];
bool isIn[NMAX];
int level[NMAX];
int father[LOGMAX][NMAX];
void dfs(int node, int parent) {
for(auto child : edges[node]) {
if(child.first != parent) {
father[0][child.first] = node;
level[child.first] = level[node] + 1;
dfs(child.first, node);
}
}
}
void make_fathers(int root, int n) {
level[root] = 0;
father[0][root] = 0;
dfs(root, -1);
for(int i = 1; i < LOGMAX; i++) {
for(int j = 0; j < n; j++) {
father[i][j] = father[i - 1][father[i - 1][j]];
}
}
}
int lca(int a, int b) {
if(level[a] > level[b])
swap(a, b);
int diff = level[b] - level[a];
for(int i = 0; i < LOGMAX; i++) {
if(diff & (1 << i))
b = father[i][b];
}
if(a == b)
return a;
for(int i = LOGMAX - 1; i >= 0; i--) {
if(father[i][a] != father[i][b]) {
a = father[i][a];
b = father[i][b];
}
}
return father[0][a];
}
int dist(int a, int b) {
return level[a] + level[b] - 2 * level[lca(a, b)];
}
int dfsCalcSize(int node, int parent) {
sz[node] = 1;
for(auto child : edges[node]) {
if(child.first != parent && isIn[child.first]) {
sz[node] += dfsCalcSize(child.first, node);
}
}
return sz[node];
}
int dfsDetCentroid(int node, int parent) {
for(auto child : edges[node]) {
if(child.first != parent && sz[child.first] > totalSize / 2 && isIn[child.first]) {
return dfsDetCentroid(child.first, node);
}
}
return node;
}
void computeDist(int centroid, int node, int parent, int depth, long long sum) {
distCentroidSubtree[centroid].push_back({sum, dist(centroid, node)});
for(auto child : edges[node]) {
if(isIn[child.first] && child.first != parent) {
computeDist(centroid, child.first, node, depth + 1, sum + child.second);
}
}
}
void decompose(int root, int parent) {
totalSize = dfsCalcSize(root, root);
int centroid = dfsDetCentroid(root, root);
computeDist(centroid, centroid, centroid, 0, 0);
isIn[centroid] = false;
centroidParent[centroid] = parent;
for(auto child : edges[centroid]) {
if(isIn[child.first])
decompose(child.first, centroid);
}
}
bool cmp(pair<long long, int> a, pair<long long, int> b) {
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
int best_path(int n, int k, int h[][2], int len[]) {
for(int i = 0; i < n - 1; i++) {
edges[h[i][0]].push_back({h[i][1], len[i]});
edges[h[i][1]].push_back({h[i][0], len[i]});
}
make_fathers(0, n);
for(int i = 0; i < n; i++)
isIn[i] = true;
decompose(0, -1);
int answer = INF;
for(int i = 0; i < n; i++) {
sort(distCentroidSubtree[i].begin(), distCentroidSubtree[i].end(), cmp);
/*cout << i << " : " << endl;
for(int st = 0; st < distCentroidSubtree[i].size(); st++)
cout << distCentroidSubtree[i][st].first << ' ';
cout << endl;*/
int dr = distCentroidSubtree[i].size() - 1;
for(int st = 0; st < distCentroidSubtree[i].size(); st++) {
while(dr > st && distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first > k)
dr--;
if(distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first == k)
answer = min(answer, distCentroidSubtree[i][st].second + distCentroidSubtree[i][dr].second);
}
}
if(answer == INF)
answer = -1;
return answer;
}
/*int h[NMAX][2];
int len[NMAX];
int main() {
int n, k;
cin >> n >> k;
for(int i = 0; i < n - 1; i++)
cin >> h[i][0] >> h[i][1];
for(int i = 0; i < n - 1; i++)
cin >> len[i];
cout << best_path(n, k, h, len);
return 0;
}*/
