#include <race.h>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define MAXN 200002
vii adjList[MAXN];
int treeSize[MAXN];
int getSize(int node, int parent, unordered_set<int> ignore) {
int size = 1;
for(ii connection : adjList[node]) {
int adj = connection.first;
if(adj == parent) {
continue;
}
if(ignore.count(adj) == 1) {
continue;
}
size += getSize(adj,node,ignore) + connection.second;
}
treeSize[node] = size;
return size;
}
int getCentroid(int node, int parent, int fullSize, unordered_set<int> ignore) {
for(ii connection : adjList[node]) {
int adj = connection.first;
if(adj == parent) {
continue;
}
if(ignore.count(adj) == 1) {
continue;
}
if(treeSize[adj] * 2 > fullSize) {
int res = getCentroid(adj,node,fullSize,ignore);
//cout << "getCentroid(" << node << ") returned " << res << endl;
return res;
}
}
cout << node << endl;
return node;
}
unordered_map<int,int> getPathLengths(int node, int parent, unordered_set<int> ignore,
int maxValue) {
unordered_map<int,int> results;
if(maxValue < 0) {
return results;
}
results[0] = 0;
for(ii connection : adjList[node]) {
int adj = connection.first;
int weight = connection.second;
if(adj == parent) {
continue;
}
if(ignore.count(adj) == 1) {
continue;
}
unordered_map<int,int> sub = getPathLengths(adj,node,ignore, maxValue - weight);
for(auto& it : sub) {
int total = weight + it.first;
if(results.count(total) == 0 || results[total] > (1 + it.second)) {
results[total] = 1 + it.second;
}
}
}
return results;
}
int k;
int solveFor(int treeStart, int parent, unordered_set<int> ignore) {
//cerr << "solveFor " << treeStart << endl;
if(ignore.count(treeStart) == 1) {
return 2 * MAXN;
}
getSize(treeStart,parent,ignore);
int centroid = getCentroid(treeStart,parent,treeSize[treeStart],ignore);
int childMin = MAXN * 2;
ignore.insert(centroid);
for(ii connection : adjList[centroid]) {
int adj = connection.first;
int res = solveFor(adj,centroid,ignore);
//cout << "child " << adj << " res " << res << endl;
childMin = min(childMin, res);
}
//cout << "starting cross node for " << treeStart << endl;
unordered_map<int,int> allResults;
allResults[0] = 0;
for(ii connection : adjList[centroid]) {
int adj = connection.first;
if(ignore.count(adj) == 1) {
continue;
}
unordered_map<int,int> newResults;
for(auto& it : getPathLengths(adj,centroid, ignore,k)) {
int weight = it.first + connection.second;
int length = it.second + 1;
if(allResults.count(k - weight) != 0) {
childMin = min(childMin, allResults[k - weight] + length);
}
newResults[weight] = length;
}
for(auto& it : newResults) {
if(allResults.count(it.first) == 0 || allResults[it.first] > it.second) {
//cout << "added " << it.first << " with " << it.second << " paths" << endl;
allResults[it.first] = it.second;
}
}
}
ignore.erase(centroid);
//cerr << "solveFor " << treeStart << " result " << childMin << endl;
return childMin;
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i < N - 1; ++i) {
adjList[H[i][0]].push_back({H[i][1],L[i]});
adjList[H[i][1]].push_back({H[i][0],L[i]});
}
k = K;
unordered_set<int> ignore;
int res = solveFor(0,-1,ignore);
if(res == 2 * MAXN) {
return -1;
} else {
return res;
}
}
