#include <iostream>
#include <vector>
#include <string>
#define debug(args...) //printf(args)
typedef std::pair<int, int> intPair;
#define forAllChild(node, code) for (intPair childPair : neighbors[node]) {\
int child = childPair.first;\
int childWeight = childPair.second;\
if (child == parent.get(node)) continue;\
if (removed.get(child)) continue;\
code;\
}
const int MAX_N = 1000000 + 10;
const int INF = 1000000000;
template<typename T>
class SpecialVector {
private:
int time;
T values[MAX_N];
T standard;
int lastChanged[MAX_N];
public:
SpecialVector(T val) {
time = 1;
standard = val;
}
T get(int i) {
if (i < 0 || i >= MAX_N) return standard;
if (lastChanged[i] == time) return values[i];
return standard;
}
void set(int i, T v) {
if (i < 0 || i >= MAX_N) return;
values[i] = v;
lastChanged[i] = time;
}
bool defined(int i) {
if (i < 0 || i >= MAX_N) return false;
return lastChanged[i] == time;
}
void clear() {
time++;
}
};
int n;
int k;
std::vector<intPair> neighbors[MAX_N];
SpecialVector<int> parent(-1);
SpecialVector<int> parentWeight(-1);
SpecialVector<bool> removed(false);
SpecialVector<int> lengths(-1);
SpecialVector<int> lengthMap(-1);
namespace CentroidDecomposition {
int findBetterCentroid(int node, int root) {
forAllChild(node, {
if (lengths.get(child) > lengths.get(root)/2) return child;
});
return -1;
}
int findCentroid(int root) {
int node = root;
while (findBetterCentroid(node, root) != -1) {
debug("found better centroid for %d (root: %d)\n", node, root);
node = findBetterCentroid(node, root);
}
debug("root %d, found centroid %d\n", root, node);
return node;
}
}
void setMin(int &a, int b) {
a = std::min(a, b);
}
void findParents(int node) {
lengths.set(node, 1);
forAllChild(node, {
parent.set(child, node);
parentWeight.set(child, childWeight);
findParents(child);
lengths.set(node, lengths.get(node) + lengths.get(child));
});
}
int getMin(int node, int depth, int distance) {
int minimum;
if (lengthMap.defined(k - distance)) {
minimum = depth + lengthMap.get(k - distance);
} else {
minimum = INF;
}
forAllChild(node, {
int childMinumum = getMin(child, depth + 1, distance + childWeight);
setMin(minimum, childMinumum);
});
return minimum;
}
void addToMapping(int node, int depth, int distance) {
if (lengthMap.get(distance) > depth || !lengthMap.defined(distance)) {
lengthMap.set(distance, depth);
}
forAllChild(node, {
addToMapping(child, depth + 1, distance + childWeight);
});
}
int getMinimumLength(int root) {
parent.clear();
lengths.clear();
findParents(root);
int centroid = CentroidDecomposition::findCentroid(root);
removed.set(centroid, true);
lengthMap.clear();
lengthMap.set(0, 0);
lengths.clear();
parent.clear();
int minimum = INF;
for (intPair neighborPair : neighbors[centroid]) {
int neighbor = neighborPair.first;
int neighborWeight = neighborPair.second;
if (removed.get(neighbor)) continue;
findParents(neighbor);
int neighborMinimum = getMin(neighbor, 1, neighborWeight);
setMin(minimum, neighborMinimum);
addToMapping(neighbor, 1, neighborWeight);
}
for (intPair neighborPair : neighbors[centroid]) {
int neighbor = neighborPair.first;
int neighborWeight = neighborPair.second;
if (removed.get(neighbor)) continue;
int neighborMinimum = getMinimumLength(neighbor);
setMin(minimum, neighborMinimum);
}
debug("root %d, centroid %d, returning %d\n", root, centroid, minimum);
return minimum;
}
void printRepeated(std::string s, int x) {
for (int i = 0; i < x; i++) printf("%s", s.c_str());
}
void printTree(int node, int depth=0) {
printRepeated("- ", depth);
printf("%d\n", node);
forAllChild(node, {
printTree(child, depth + 1);
});
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n - 1; i++) {
int a = H[i][0];
int b = H[i][1];
int w = L[i];
neighbors[a].push_back(std::make_pair(b, w));
neighbors[b].push_back(std::make_pair(a, w));
}
//findParents(0);
//printTree(0);
int answer = getMinimumLength(0);
if (answer == INF) answer = -1;
return answer;
}
