#include <bits/stdc++.h>
#include "race.h"
#define debug(args...) //fprintf(stderr, args)
#define INF 1000000010
using namespace std;
const int MAXN = 200010;
vector<int> grafo[MAXN], pesos[MAXN];
int marc[1000010], ultimo[1000010], sub[MAXN];
int MarcCentroid[MAXN];
int cnt = 0;
int K;
int acessa(int pos)
{
if (ultimo[pos] == cnt) return marc[pos];
return INF;
}
void muda(int pos, int val)
{
marc[pos] = val;
ultimo[pos] = cnt;
}
void zera(){cnt++;}
int dfsCentroid(int v, int p)
{
sub[v] = 1;
for (auto viz : grafo[v])
{
if (viz == p) continue;
if (MarcCentroid[viz]) continue;
sub[v] += dfsCentroid(viz, v);
}
return sub[v];
}
int findCentroid(int v, int p, int n)
{
for (auto viz : grafo[v])
{
if (viz == p) continue;
if (MarcCentroid[viz]) continue;
if (sub[viz] > n / 2) return findCentroid(viz, v, n);
}
return v;
}
int dfsTesta(int v, int p, int dist, int prof)
{
if (dist > K) return INF;
debug("\tmarc[%d]: %d, prof: %d, dist: %d\n",K - dist,acessa(K - dist),prof,dist);
for (int i = 0; i < grafo[v].size(); i++)
{
int viz = grafo[v][i];
int peso = pesos[v][i];
if (viz == p) continue;
if (MarcCentroid[viz]) continue;
//if (acessa(K - dist) == INF) return dfsTesta(viz, v, dist + peso, prof+1);
return min(prof + acessa(K - dist), dfsTesta(viz, v, dist + peso, prof+1));
}
//if (acessa(K - dist) == INF) return INF;
return prof + acessa(K - dist);
}
void dfsMarca(int v, int p, int dist, int prof)
{
muda(dist, min(acessa(dist), prof));
debug("\tmarc[%d]: %d, prof: %d, dist: %d\n",dist,acessa(dist),prof,dist);
for (int i = 0; i < grafo[v].size(); i++)
{
int viz = grafo[v][i];
if (viz == p) continue;
if (MarcCentroid[viz]) continue;
if (dist + pesos[v][i] > K) continue;
dfsMarca(viz, v, dist + pesos[v][i], prof+1);
}
}
int divide_and_conquer(int v, int p)
{
zera();
muda(0, 0);
int n = dfsCentroid(v, p);
int c = findCentroid(v, p, n);
MarcCentroid[c] = 1;
int resp = INF;
debug("Centroid: %d\n",c);
for (int i = 0; i < grafo[c].size(); i++)
{
int viz = grafo[c][i];
int peso = pesos[c][i];
if (MarcCentroid[viz]) continue;
debug("\tviz: %d\n",viz);
debug("\tTesta:\n");
resp = min(resp, dfsTesta(viz, c, peso, 1));
debug("\tMarca:\n");
dfsMarca(viz, c, peso, 1);
}
for (int i = 0; i < grafo[c].size(); i++)
{
int viz = grafo[c][i];
if (viz == p) continue;
if (MarcCentroid[viz]) continue;
resp = min(resp, divide_and_conquer(viz, c));
}
//debug("Centroid: %d, resp: %d\n",c,resp);
return resp;
}
int best_path(int n, int k, int edges[][2], int cost[])
{
int N = n; K = k;
for (int i = 0; i < N-1; i++)
{
int X, Y, P;
X = edges[i][0];
Y = edges[i][1];
P = cost[i];
grafo[X].push_back(Y);
pesos[X].push_back(P);
grafo[Y].push_back(X);
pesos[Y].push_back(P);
}
int resp = divide_and_conquer(1, 1);
if (resp >= INF) return -1;
else return resp;
}
