#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int msz = 2e5 + 5;
const int lg = 25;
struct edge{
int to, t;
edge(int a, int b){
to = a; t = b;
}
};
vector<edge> g[msz];
vector<int> cl[lg], out, sz;
void fill(int v, int pr){
sz[v] = 1;
for (auto i: g[v]){
if (i.to == pr || out[i.to]) continue;
fill(i.to, v);
sz[v] += sz[i.to];
}
}
int find(int v, int pr, int& x){
for (auto i: g[v]){
if (i.to == pr || out[i.to]) continue;
if (2 * sz[i.to] >= x) return find(i.to, v, x);
}
return v;
}
void build(int v, int cnt){
fill(v, 0);
int u = find(v, 0, sz[v]);
out[u] = cnt++;
cl[out[u]].push_back(u);
for (auto i: g[u]){
if (out[i.to]) continue;
build(i.to, cnt);
}
}
vector<ll> weight;
vector<pair<int, int>> p;
vector<bool> used;
void fill_dfs(int v, int pr){
for (auto i: g[v]){
if (i.to == pr || used[i.to]) continue;
weight[i.to] = weight[v] + i.t;
fill_dfs(i.to, v);
}
}
void add(int v, int pr, int cnt){
p.push_back({v, cnt++});
for (auto i: g[v]){
if (i.to == pr || used[i.to]) continue;
add(i.to, v, cnt);
}
}
int ans = msz, l;
void solve(int v, int cnt){
weight[v] = 0;
used[v] = true;
fill_dfs(v, 0);
map<ll, int> mp;
for (auto i: g[v]){
if (used[i.to]) continue;
add(i.to, 0, 1);
for (auto j: p){
if (weight[j.first] > l) continue;
if (weight[j.first] == l){
ans = min(ans, j.second);
continue;
}
int x = mp[l - weight[j.first]];
if (x > 0) ans = min(ans, j.second + x);
}
for (auto j: p){
int val = mp[weight[j.first]];
if (!val){
mp[weight[j.first]] = j.second;
continue;
}
mp[weight[j.first]] = min(val, j.second);
}
p.clear();
}
}
int n;
void best_path(int ns, int ks, vector<pii> hs, vector<int> ls){
n = ns; l = ks;
for (int i = 0; i < hs.size(); i++){
auto [u, v] = hs[i];
u++; v++;
g[u].push_back({v, ls[i]});
g[v].push_back({u, ls[i]});
}
out.assign(n + 1, 0);
sz.resize(n + 1);
build(1, 1);
weight.resize(n + 1);
used.assign(n + 1, false);
for (int i = 1; i < lg; i++){
for (int j: cl[i]){
solve(j, 1);
}
}
if (ans == msz){
cout<<-1;
return;
}
cout<<ans;
}
// Old code
Compilation message
race.cpp: In function 'void best_path(int, int, std::vector<std::pair<int, int> >, std::vector<int>)':
race.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i = 0; i < hs.size(); i++){
| ~~^~~~~~~~~~~
/usr/bin/ld: /tmp/ccm130LE.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status
