#include <bits/stdc++.h>
#include "race.h"
#define INF 1000000010
using namespace std;
const int MAXN = 200010;
vector<int> grafo[MAXN], pesos[MAXN];
int marc[MAXN], ultimo[MAXN], 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)
{
if (dist > K) return INF;
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(dist) == INF || acessa(K - dist) == INF) return dfsTesta(viz, v, dist + peso);
return min(acessa(dist) + acessa(K - dist), dfsTesta(viz, v, dist + peso));
}
if (acessa(dist) == INF || acessa(K - dist) == INF) return INF;
return acessa(dist) + acessa(K - dist);
}
void dfsMarca(int v, int p, int 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;
if (acessa(dist + pesos[v][i]) > acessa(dist) + 1 || acessa(dist + pesos[v][i]) == INF) muda(dist + pesos[v][i], acessa(dist) + 1);
dfsMarca(viz, v, dist + pesos[v][i]);
}
}
int divide_and_conquer(int v, int p)
{
zera();
muda(0, 0);
int n = dfsCentroid(v, p);
int c = findCentroid(v, p, n);
if (p == -1) p = c;
MarcCentroid[c] = 1;
int resp = INF;
for (int i = 0; i < grafo[c].size(); i++)
{
int viz = grafo[c][i];
int peso = pesos[c][i];
if (MarcCentroid[viz]) continue;
muda(peso, 1);
resp = min(resp, dfsTesta(viz, c, peso));
dfsMarca(viz, c, peso);
}
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));
}
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;
}
