#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int NMAX = 1e5;
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 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, depth});
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]});
}
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;
}*/
