#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
map<long long, int> stl[200'000];
vector<pair<int,int>> adj[200'000];
int dep[200'000], ans = 1e9;
long long dist[200'000], k;
void init(int u = 0, int p = 0) {
stl[u][dist[u]] = dep[u];
for (auto [v, w] : adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dist[v] = dist[u] + w;
init(v, u);
}
}
void dfs(int u = 0, int p = 0) {
long long target = k + 2*dist[u];
for (auto [v, w] : adj[u]) if (v != p) {
dfs(v, u);
if (stl[v].size() > stl[u].size()) swap(stl[u], stl[v]);
for (auto [len, edges] : stl[v]) {
if (stl[u].count(target - len)) {
cout << u << " " << v << "\n";
cout << len << " " << target - len << '\n';
ans = min(ans, stl[u][target - len] + edges - 2*dep[u]);
}
}
for (auto [len, edges] : stl[v]) {
if (stl[u].count(len)) {
stl[u][len] = min(stl[u][len], edges);
} else {
stl[u][len] = edges;
}
}
}
// cout << u << ":\n";
// for (auto [len, edges] : stl[u]) cout << len << " " << edges << "\n";
// cout << '\n';
}
int best_path(int n, int _k, vector<vector<int>> h, vector<int> l) {
k = _k;
for (int i = 0; i < n-1; i++) {
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
init();
dfs();
return ans == 1e9 ? -1 : ans;
}
Compilation message
/usr/bin/ld: /tmp/ccpoTLii.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
