#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 500'001;
const int K = 21;
vector<pair<ll, ll>> g[MAXN];
vector<ll> g2[MAXN];
ll sz[MAXN], tin[MAXN], tout[MAXN], up[MAXN][K], idx[MAXN], node[MAXN], par[MAXN], timer = 1, n;
ll mn[MAXN];
bool vis[MAXN];
ll depth[MAXN];
void calc_sz(int u, int p = -1) {
sz[u] = 1;
for (auto [v, d] : g[u]) {
if (vis[v] || v == p) continue;
calc_sz(v, u);
sz[u] += sz[v];
}
}
void dfs(int u, int p = -1) {
tin[u] = timer++;
for (auto [v, d] : g[u]) {
if (v == p) continue;
depth[v] = depth[u] + d;
dfs(v, u);
up[v][0] = u;
}
tout[u] = timer++;
for (int i = 1; i < K; i++) {
up[u][i] = up[up[u][i-1]][i-1];
}
}
void dfs2(int u) {
for (int v : g2[u]) {
par[v] = u;
dfs2(v);
}
}
int findc(int u, int p = -1, int siz) {
for (auto [v, d] : g[u]) {
if (!vis[v] && v != p && sz[v] > siz/2) return findc(v, u);
}
return u;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = K-1; i >= 0; i--) {
if (!is_ancestor(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
ll get_dist(int u, int v) {
int l = lca(u, v);
return depth[u] + depth[v] - 2ll * depth[l];
}
int build_tree(int u) {
calc_sz(u);
int c = findc(u, -1, sz[u]);
idx[c] = timer;
node[timer] = c;
timer++;
vis[c] = true;
for (auto [v, d] : g[c]) {
if (!vis[v]) {
int x = build_tree(v);
g2[idx[c]].emplace_back(idx[x]);
}
}
return c;
}
void Init(int N, int A[], int B[], int D[]) {
fill(mn, mn+MAXN, 1e16);
n = N;
for (int i = 0; i < n-1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
dfs(0);
timer = 1;
build_tree(0);
dfs2(1);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = 1e16;
auto work = [&](int u, int goal, bool rem) {
while (u != 0) {
mn[u] = rem ? 1e16 : min(mn[u], get_dist(node[u], goal));
u = par[u];
}
};
auto calc = [&](int u, int goal) {
while (u != 0) {
ans = min(ans, get_dist(node[u], goal) + mn[u]);
u = par[u];
}
};
for (int i = 0; i < T; i++) {
work(idx[Y[i]], Y[i], false);
}
for (int i = 0; i < S; i++) {
calc(idx[X[i]], X[i]);
}
for (int i = 0; i < T; i++) {
work(idx[Y[i]], Y[i], true);
}
return ans;
}
Compilation message
factories.cpp:47:34: error: default argument missing for parameter 3 of 'int findc(int, int, int)'
47 | int findc(int u, int p = -1, int siz) {
| ~~~~^~~
factories.cpp:47:22: note: ...following parameter 2 which has a default argument
47 | int findc(int u, int p = -1, int siz) {
| ~~~~^~~~~~
