#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<vector<pair<ll, ll>>> grafo;
void dfs2(ll src, ll parent, ll currPathTam, ll currPathArestas);
vector<ll> subtrees;
vector<bool> visited;
ll minCam = INT_MAX;
unordered_map<ll, ll> melhor; // melhor caminho que chega naquela raiz com tamanho sendo a chave e o número de arestas sendo o valor
void calc_subtrees(ll src, ll parent){
subtrees[src] = 1;
for (auto& vz: grafo[src]){
ll v = vz.first;
if (v == parent || visited[v]) continue; // <-- correção: pula parent e nós bloqueados
calc_subtrees(v, src);
subtrees[src] += subtrees[v];
}
}
ll centroid(ll src, ll parent, ll subTreeSize){
for (auto vz: grafo[src]){
ll v = vz.first;
if (v == parent || visited[v]) continue; // <-- pular parent e bloqueados antes de usar subtrees
if (subtrees[v] > subTreeSize/2){
return centroid(v, src, subTreeSize);
}
}
return src;
}
ll find_centroid(ll beg, ll parent){
// não use clear(); garanta o tamanho correto
subtrees.assign(grafo.size(), 0); // <-- correção: garante espaço
calc_subtrees(beg, parent);
return centroid(beg, -1, subtrees[beg]);
}
void dfs1(ll src, ll parent, ll currPathTam, ll currPathArestas, ll K){
if (visited[src]) return; // evita entrar em nós já bloqueados
if (melhor.find(K - currPathTam) != melhor.end())
minCam = min(minCam, currPathArestas + melhor[K - currPathTam]);
for (int i = 0; i< (int)grafo[src].size() ; i++){
auto [vz, w] = grafo[src][i];
if (parent == vz || visited[vz]) continue; // pula parent e bloqueados
dfs1(vz, src, currPathTam + w, currPathArestas + 1, K);
}
}
void dfs2(ll src, ll parent, ll currPathTam, ll currPathArestas){
if (visited[src]) return; // evita inserir caminhos de componentes já bloqueadas
if (melhor.find(currPathTam)!= melhor.end())
melhor[currPathTam ] = min(melhor[currPathTam], currPathArestas);
else
melhor[currPathTam] = currPathArestas;
for (auto &[vz, w]: grafo[src]){
if (vz == parent || visited[vz]) continue;
dfs2(vz, src, currPathTam + w, currPathArestas + 1);
}
}
void solve(ll start, ll K){
ll cntd = find_centroid(start, -1);
visited[cntd] = true;
melhor.clear();
melhor[0] = 0; // <-- caso base: caminho de soma 0 com 0 arestas
for (auto [v, w] : grafo[cntd]){
if (visited[v]) continue;
dfs1(v, cntd, w, 1, K);
dfs2(v, cntd, w, 1);
}
for (auto [v, w] : grafo[cntd]){
if (!visited[v]){
solve(v, K);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
minCam = INT_MAX;
visited.assign(N, false);
subtrees.assign(N, 0);
grafo.resize(N);
for (int i = 0; i < N - 1; i++)
{
grafo[H[i][0]].push_back({H[i][1], L[i]});
grafo[H[i][1]].push_back({H[i][0], L[i]});
}
solve(0,K);
return (minCam == INT_MAX ? -1 : minCam);
}
