#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const int MAXN = 2e5;
int ans;
vector<pair<int, int>> G[MAXN];
int sz[MAXN];
int target;
int sz_above[MAXN];
int par[MAXN];
queue<int> q;
bool blocked[MAXN];
struct Path
{
int len, val;
};
vector<Path> paths;
const int MAX = 1e6+1;
int have[MAX];
void dfs(int u)
{
sz[u] = 1;
for (auto [v, w] : G[u])
if (!blocked[v] and v != par[u])
{
par[v] = u;
dfs(v);
sz[u] += sz[v];
}
}
int get_centroid(int source)
{
int centroid = source;
int bst = sz[source];
sz_above[source] = 0;
q.push(source);
while (SZ(q))
{
int u = q.front(); q.pop();
int cur_sz = sz_above[u];
for (auto [v, w] : G[u])
if (!blocked[v] and v != par[u])
{
cur_sz = max(cur_sz, sz[v]);
sz_above[v] = sz_above[u] + sz[u] - sz[v];
q.push(v);
}
if (cur_sz < bst)
bst = cur_sz, centroid = u;
}
return centroid;
}
void dfs2(int u, int p, int depth, int cur_weight)
{
if (cur_weight > target)
return ;
paths.push_back({depth, cur_weight});
for (auto [v, w] : G[u])
if (v != p and !blocked[v])
dfs2(v, u, depth + 1, cur_weight + w);
}
void run_centroid(int source)
{
par[source] = -1;
dfs(source);
vector<int> to_reset;
int centroid = get_centroid(source);
have[0] = 0;
for (auto [v, w] : G[centroid])
if (!blocked[v])
{
dfs2(v, centroid, 1, w);
for (auto [len, val] : paths)
if (have[target - val] != -1)
ans = min(ans, have[target - val] + len);
for (auto [len, val] : paths)
{
if (have[val] != -1)
have[val] = min(have[val], len);
else
{
have[val] = len;
to_reset.push_back(val);
}
}
paths.clear();
}
for (auto v : to_reset)
have[v] = -1;
blocked[centroid] = true;
for (auto [v, _] : G[centroid])
if (!blocked[v])
run_centroid(v);
}
int best_path(int nb_villes, int _target, int edges[][2], int lengths[])
{
for (int i(0); i < MAX; ++i)
have[i] = -1;
target = _target;
ans = 1e9;
for (int i(0); i < nb_villes - 1; ++i)
{
G[edges[i][0]].emplace_back(edges[i][1], lengths[i]);
G[edges[i][1]].emplace_back(edges[i][0], lengths[i]);
}
run_centroid(0);
if (ans == 1e9)
ans = -1;
return ans;
}
