#include <bits/stdc++.h>
#include "race.h"
using namespace std;
/* TYPES */
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
/* FUNCTIONS */
#define f(i, s, e) for (long long int i = s; i < e; i++)
#define cf(i, s, e) for (long long int i = s; i <= e; i++)
#define rf(i, e, s) for (long long int i = e - 1; i >= s; i--)
#define pb push_back
/* UTILS */
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
/* PRINT */
template <class T>
void print_v(vector<T> &v)
{
cout << "{";
for (auto x : v)
cout << x << ",";
cout << "\b}";
}
// Centroid decomposition
//
// decomp(0, k) computa numero de caminhos com 'k' arestas
// Mudar depois do comentario
//
// O(n log(n))
#define MAX 200010
#define MAXK 1000010
vector<pair<int, int>> g[MAX];
int sz[MAX], rem[MAX];
int melhor[MAXK], flag[MAXK] = {0};
int ans = MAX, flagAtual = 0;
int getMelhor(int k)
{
if (flag[k] == flagAtual)
return melhor[k];
return MAX;
}
void setMelhor(int k, int x)
{
melhor[k] = x;
flag[k] = flagAtual;
}
// void dfs(vector<int> &path, int i, int l = -1, int d = 0)
// {
// path.push_back(d);
// for (int j : g[i])
// if (j != l and !rem[j])
// dfs(path, j, i, d + 1);
// }
void dfs2(int i, int k, int peso, int tam = 1, int l = -1)
{
if (peso > k)
return;
int currentMelhor = getMelhor(peso);
setMelhor(peso, min(currentMelhor, tam));
for (auto &[j, w] : g[i])
if (j != l and !rem[j])
dfs2(j, k, peso + w, tam + 1, i);
}
void dfs1(int i, int k, int peso, int tam = 1, int l = -1)
{
if (peso > k)
return;
int remainingK = k - peso;
ans = min(ans, getMelhor(remainingK) + tam);
for (auto &[j, w] : g[i])
if (j != l and !rem[j])
dfs1(j, k, peso + w, tam + 1, i);
}
int dfs_sz(int i, int l = -1)
{
sz[i] = 1;
for (auto &[j, w] : g[i])
if (j != l and !rem[j])
sz[i] += dfs_sz(j, i);
return sz[i];
}
int centroid(int i, int l, int size)
{
for (auto &[j, w] : g[i])
if (j != l and !rem[j] and sz[j] > size / 2)
return centroid(j, i, size);
return i;
}
void decomp(int i, int k)
{
int c = centroid(i, i, dfs_sz(i));
rem[c] = 1;
flagAtual++;
setMelhor(0, 0);
for (auto &[j, w] : g[c])
if (!rem[j])
{
dfs1(j, k, w);
dfs2(j, k, w);
ans = min(ans, getMelhor(k));
}
for (auto &[j, w] : g[c])
if (!rem[j])
decomp(j, k);
rem[c] = 0;
}
int best_path(int N, int K, int H[][2], int L[])
{
int A, B;
for (int i = 0; i < N; i++)
{
A = H[i][0], B = H[i][1];
g[A].push_back({B, L[i]});
g[B].push_back({A, L[i]});
}
decomp(0, K);
return ans == MAX ? -1 : ans;
}
