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