#include <bits/stdc++.h>
using namespace std;
#define wait() system("pause")
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define read(s) freopen(s, "r", stdin)
#define write(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define int long long
#define inf 1000000000000000000LL
const int maxn = 200010;
bool onCtree[maxn]; int n, k;
vector<pair<int, int>> v[maxn];
vector<int> ctree[maxn], subtree[maxn];
int level[maxn], T[19][maxn], sub[maxn], D[maxn], parent[maxn];
map<int, int> mp; int ret = inf;
vector<int> eulerTour; int lg[maxn*2], where[maxn], table[19][maxn*2];
void preCalc(int p, int node, int l, int d) {
level[node] = l; eulerTour.push_back(node);
D[node] = d, T[0][node] = parent[node] = p;
for(auto b : v[node]) {
if(b.first != p) {
preCalc(node, b.first, l+1, d+b.second);
eulerTour.push_back(node);
}
}
}
int MIN(int a, int b) { // I can easily believe that where O(1)
// lca needed there is a level[] array :/
return ( level[a] < level[b] ? a : b ) ;
}
void makeTable() {
int N = eulerTour.size()-1;
for(int i=0; i<maxn; i++) where[i] = inf;
for(int i=0; i<=N; i++) where[eulerTour[i]] = min(where[eulerTour[i]], i);
for(int i=0; i<=N; i++) table[0][i] = eulerTour[i];
lg[1] = 0; for(int i=2; i<=N; i++) lg[i] = lg[i >> 1] + 1;
for(int p=1; p<20; p++) {
for(int i=0; i+(1<<p)-1<=N; i++) {
table[p][i] = MIN(table[p-1][i], table[p-1][i+(1<<(p-1))]);
}
}
}
int getMin(int l, int r) {
int k = lg[r-l+1];
return MIN(table[k][l], table[k][r-(1<<k)+1]);
}
int __lca(int a, int b) {
if(where[a] > where[b]) swap(a, b);
return getMin(where[a], where[b]);
}
int cost(int x, int y) {
return D[x] + D[y] - 2 * D[__lca(x, y)];
}
int dist(int x, int y) {
return level[x] + level[y] - 2 * level[__lca(x, y)];
}
void dfs(int p, int node) {
sub[node] = 1;
for(auto b : v[node]) {
if(!onCtree[b.first] and p != b.first) {
dfs(node, b.first);
sub[node] += sub[b.first];
}
}
}
int decompose(int p, int node, int sz) {
for(auto b : v[node]) {
if(!onCtree[b.first] and b.first != p and sub[b.first] > sz/2) {
return decompose(node, b.first, sz);
}
}
onCtree[node] = true;
for(auto b : v[node]) {
if(!onCtree[b.first]) {
dfs(node, b.first);
ctree[node].push_back(decompose(node, b.first, sub[b.first]));
}
} return node;
}
void add(int node) {
subtree[node].push_back(node);
for(auto b : ctree[node]) {
add(b);
for(auto x : subtree[b]) {
subtree[node].push_back(x);
}
}
}
void solve() {
preCalc(-1,1,0,0);
//process();
makeTable();
dfs(-1,1);
int root = decompose(-1,1, sub[1]);
add(root);
for(int i=1; i<=n; i++) ctree[i].reserve(ctree[i].size());
for(int i=1; i<=n; i++) subtree[i].reserve(subtree[i].size());
for(int i=1; i<=n; i++) {
for(auto b : ctree[i]) {
for(auto node : subtree[b]) {
//int d = cost(i, node);
int lca = __lca(i, node);
int d = D[i] + D[node] - 2 * D[lca];
if(mp.find(k-d) != mp.end()) {
//ret = min(ret, dist(i, node)+mp[k-d]);
ret = min(ret, level[i] + level[node] - 2 * level[lca] + mp[k-d]);
}
}
for(auto node : subtree[b]) {
//int d = cost(i, node);
int lca = __lca(i, node);
int d = D[i] + D[node] - 2 * D[lca];
if(mp.find(d) != mp.end()) {
mp[d] = min(mp[d], level[i] + level[node] - 2 * level[lca]);
} else mp[d] = level[i] + level[node] - 2 * level[lca];
}
}
if(mp.find(k) != mp.end()) {
ret = min( ret , mp[k] );
}
mp.clear();
}
}
int best_path(int N, int K,, int H[][], int L[]) {
n = N, k = K;
for(int i=0; i<n-1; i++) {
int x = H[i][0]+1, y = H[i][1]+1, w = L[i];
v[x].push_back({y, w});
v[y].push_back({x, w});
}
if(k==0) return 0;
solve();
if(ret == inf) return -1;
return ret;
}
/*
int32_t main () {
cin>>n>>k;
for(int i=1; i<n; i++) {
int x, y, w; scanf("%lld%lld%lld", &x, &y, &w);
x++, y++;
v[x].push_back({y, w});
v[y].push_back({x, w});
}
if(k==0) {
puts("0");
return 0;
}
solve();
if(ret == inf) {
puts("-1");
} else {
printf("%lld\n", ret);
}
//wait();
return 0;
}
*/
Compilation message
race.cpp:142:28: error: expected identifier before ',' token
int best_path(int N, int K,, int H[][], int L[]) {
^
race.cpp:142:38: error: declaration of 'H' as multidimensional array must have bounds for all dimensions except the first
int best_path(int N, int K,, int H[][], int L[]) {
^
race.cpp:142:39: error: expected ')' before ',' token
int best_path(int N, int K,, int H[][], int L[]) {
^
race.cpp:12:13: error: expected unqualified-id before 'long'
#define int long long
^
race.cpp:142:41: note: in expansion of macro 'int'
int best_path(int N, int K,, int H[][], int L[]) {
^~~
