#include <bits/stdc++.h>
#include "factories.h"
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 5e5 + 128;
const ll INF = 1e15 + 128;
const int LOG = 19;
int lift[N][LOG], depth[N];
ll d[N];
vector < pair<int, int> > g[N];
int n, q;
bool was[N];
int h[N];
ll res[N];
void init(int v, ll val = 0, int p = 1) {
d[v] = val;
if (v != 1)
depth[v] = depth[p] + 1;
lift[v][0] = p;
for (int b = 1; b < LOG; b++)
lift[v][b] = lift[lift[v][b-1]][b-1];
for (auto& [to, len] : g[v])
if (to != p)
init(to, val+len, v);
}
int lca(int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
int k = depth[u] - depth[v];
for (int b = 0; b < LOG; b++)
if ((k >> b) & 1)
u = lift[u][b];
if (u == v)
return u;
for (int b = LOG - 1; b >= 0; b--)
if (lift[v][b] != lift[u][b])
v = lift[v][b], u = lift[u][b];
return lift[v][0];
}
ll get(int u, int v) {
return len[u]+len[v]-2*len[lca(u,v)];
}
void dfs(int v, int p = -1) {
h[v] = 1;
for (auto& [to, len] : g[v])
if (to != p && !was[to])
dfs(to, v), h[v] += h[to];
}
int find_centroid(int v, int p, int sz) {
for (auto& [to, len] : g[v])
if (to != p && h[to] > sz / 2 && !was[to])
return find_centroid(to, v, sz);
return v;
}
int p[N];
void decompose(int v, int pr = -1) {
dfs(v);
int c = find_centroid(v, -1, h[v]);
p[c] = pr;
was[c] = true;
for (auto& [to, len] : g[c])
if (!was[to])
decompose(to, c);
}
void update(int v) {
int c = v;
while (c != -1)
res[c] = min(res[c], get(c, v)), c = p[c];
}
void reset(int v) {
int c = v;
while (c != -1)
res[c] = INF, c = p[c];
}
ll get(int v) {
ll ans = INF;
int c = v;
while (c != -1)
ans = min(ans, get(c,v)+res[c]), c = p[c];
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i + 1 < n; i++) {
int u = A[i], v = B[i], w = D[i];
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
for (int i = 0; i <= n; i++)
res[i] = INF, p[i] = -1;
decompose(1);
init(1);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++)
update(X[i]);
ll tot = INF;
for (int i = 0; i < T; i++)
tot = min(tot, get(Y[i]));
for (int i = 0; i < S; i++)
reset(X[i]);
return tot;
}
Compilation message
factories.cpp: In function 'long long int get(int, int)':
factories.cpp:54:12: error: 'len' was not declared in this scope
54 | return len[u]+len[v]-2*len[lca(u,v)];
| ^~~
