#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+42;
#define pii pair<int, int>
int nbNodes, requestedSum;
vector<vector<pii>> voisinDe;
vector<int> profSubtree;
vector<bool> interdit;
int lenSubTree;
int dfs(int nde, int ansc)
{
int ans = 1;
for(pii iV : voisinDe[nde])
{
if(!interdit[iV.first] && iV.first != ansc)
{
ans += dfs(iV.first, nde);
}
}
profSubtree[nde] = ans;
return ans;
}
int getCentroid(int nde, int ansc)
{
for(pii iV : voisinDe[nde])
{
if(!interdit[iV.first] && iV.first!= ansc)
{
if(profSubtree[iV.first] > (lenSubTree)/2)
{
return getCentroid(iV.first, nde);
}
}
}
return nde;
}
vector<pii> minDistToLen;
vector<pii> toUpd;//sum, len;
int timer;
int findLenghts(int nde, int ansc, int sum, int len)
{
int ans = INF;
if(sum > requestedSum)
return INF;
if(sum == requestedSum)
return len;
toUpd.push_back({sum, len});
int sumRemain = requestedSum - sum;
if(minDistToLen[sumRemain].first == timer)
ans = len + minDistToLen[sumRemain].second;
for(pii iV : voisinDe[nde])
{
if(!interdit[iV.first] && iV.first != ansc)
{
ans = min(ans, findLenghts(iV.first, nde, sum + iV.second, len+1));
}
}
return ans;
}
int ctr = 0;
int findMinPath(int nde)
{
//printf("[centroid : %d]", nde);
int ans = INF;
for(pii iV : voisinDe[nde])
{
toUpd.clear();
ans = min(findLenghts(iV.first, nde, iV.second, 1), ans);
for(pii updAct : toUpd)
{
ctr++;
if(ctr > 50*nbNodes)
printf("error");
minDistToLen[updAct.first] = min(minDistToLen[updAct.first], {timer ,updAct.second});
}
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
nbNodes = N;
requestedSum = K;
profSubtree.resize(nbNodes);
timer = 2*nbNodes;
interdit.assign(nbNodes, false);
voisinDe.resize(nbNodes);
minDistToLen.assign(1000042, {INF, INF});
for(int i =0; i< nbNodes-1; i++)
{
voisinDe[H[i][0]].push_back({H[i][1], L[i]});
voisinDe[H[i][1]].push_back({H[i][0], L[i]});
}
deque<int> process;
lenSubTree = dfs(0, -1);
int centroid = getCentroid(0, -1);
process.push_back(centroid);
int ansMin = INF;
while (!process.empty())
{
int ndeToProcess = process.front();
process.pop_front();
interdit[ndeToProcess] = true;
int ansAct=findMinPath(ndeToProcess);
ansMin = min(ansMin, ansAct);
timer--;
for(pii iV : voisinDe[ndeToProcess])
{
if(!interdit[iV.first])
{
lenSubTree = dfs(iV.first, -1);
centroid = getCentroid(iV.first, -1);
process.push_back(centroid);
}
}
}
if(ansMin == INF)
return -1;
return ansMin;
}
