#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define siz 200000
#define pii pair<int, int>
#define ll long long
#define int ll
int n;
vector<int> graph [siz];
vector<pii> wGraph [siz];
bool isCentroid [siz];
int centroidParent [siz];
int subtreeSize [siz];
int parent [siz];
vector<vector<int>> centroidGraph;
int nodeAssignedVal [siz];
int getSubtreeSizes(int curNode) {
int locNodes = 1;
subtreeSize[curNode] = 1;
for (int newNode : graph[curNode]) {
if (newNode != parent[curNode] and !isCentroid[newNode]) {
parent[newNode] = curNode;
locNodes += getSubtreeSizes(newNode);
subtreeSize[curNode] += subtreeSize[newNode];
}
}
return locNodes;
}
int getCentroidSub(int curNode, int& totalNodes) {
bool centroidOk = true;
int counter = totalNodes-1;
for (int newNode : graph[curNode]) {
if (isCentroid[newNode] or parent[curNode] == newNode) continue;
counter -= subtreeSize[newNode];
if (subtreeSize[newNode] > (totalNodes)/2) {
centroidOk = false;
break;
}
}
if ((parent[curNode] == -1 or counter <= (totalNodes)/2) and centroidOk) return curNode;
for (int newNode : graph[curNode]) {
if (newNode != parent[curNode] and !isCentroid[newNode]) {
int res = getCentroidSub(newNode, totalNodes);
if (res != -1) return res;
}
}
return -1;
}
int getCentroid(int root) {
parent[root] = -1;
int totalNodes = getSubtreeSizes(root);
int res = getCentroidSub(root, totalNodes);
return res;
}
int generateCentroidSubtree(int curNode) {
int centroidNode = getCentroid(curNode);
isCentroid[centroidNode] = true;
for (int newNode : graph[centroidNode]) {
if (!isCentroid[newNode]) {
centroidParent[generateCentroidSubtree(newNode)] = centroidNode;
}
}
return centroidNode;
}
int centroidDecomp() {
for (int i = 0; i < n; i++) {
isCentroid[i] = false;
centroidParent[i] = -1;
}
generateCentroidSubtree(0);
centroidGraph = vector<vector<int>>(n);
int root;
for (int i = 0; i < n; i++) {
if (centroidParent[i] != -1) centroidGraph[centroidParent[i]].push_back(i);
else root = i;
}
return root;
}
void dfs(unordered_map<int, unordered_map<int, int>>& perChild, int curNode, int parentNode, int subtreeNode, int forbiddenNode, int curDist, int edgesOnPath) {
if (curNode == forbiddenNode) return;
if (subtreeNode == -1 and parentNode != -1) subtreeNode = curNode;
if (subtreeNode != -1) {
if (perChild[subtreeNode].find(curDist) == perChild[subtreeNode].end()) perChild[subtreeNode][curDist] = n;
perChild[subtreeNode][curDist] = min(perChild[subtreeNode][curDist], edgesOnPath);
perChild[subtreeNode][0] = 0;
}
for (pii newEdge : wGraph[curNode]) {
if (newEdge.first == parentNode) continue;
dfs(perChild, newEdge.first, curNode, subtreeNode, forbiddenNode, curDist+newEdge.second, edgesOnPath+1);
}
}
int best_path(int32_t ln, int32_t kval, int32_t edges [siz-1][2], int32_t edgeLen [siz-1]) {
n = ln;
for (int i = 0; i < n-1; i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
wGraph[edges[i][0]].push_back(pii(edges[i][1], edgeLen[i]));
wGraph[edges[i][1]].push_back(pii(edges[i][0], edgeLen[i]));
}
centroidDecomp();
int minEdgesInPath = n;
for (int i = 0; i < n; i++) {
unordered_map<int, unordered_map<int, int>> perChild;
dfs(perChild, i, -1, -1, centroidParent[i], 0, 0);
unordered_map<int, multiset<int>> s;
for (pair<int, unordered_map<int, int>> j : perChild) {
for (pii k : j.second) s[k.first].insert(k.second);
}
for (pair<int, unordered_map<int, int>> j : perChild) {
for (pii k : j.second) s[k.first].erase(s[k.first].find(k.second));
for (pii k : j.second) {
if (s.find(kval-k.first) != s.end() and !s[kval-k.first].empty()) {
minEdgesInPath = min(minEdgesInPath, (*(s[kval-k.first].begin()))+k.second);
}
}
for (pii k : j.second) s[k.first].insert(k.second);
}
}
if (minEdgesInPath == n) minEdgesInPath = -1;
return minEdgesInPath;
}
// int H[siz-1][2];
// int L[siz-1];
// int32_t 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 >> L[i];
// cout << best_path(N, K, H, L);
// }
