#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const long long INFF = 1e18;
vector<int> dep(500000), par(500000), tin(500000);
vector<long long> d(500000), ans(500000, INFF);
vector<vector<pair<int, int>>> sp(1000000, vector<pair<int, int>>(20));
void Init(int n, int A[], int B[], int D[]) {
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], d[i]});
g[b[i]].push_back({a[i], d[i]});
}
int tim = 0;
function<void(int, int)> dfs = [&](int x, int pr) {
sp[tim][0] = {dep[x], x};
tin[x] = tim++;
for (auto [z, c] : g[x]) {
if (z == pr) continue;
dep[z] = dep[x] + 1;
d[z] = d[x] + c;
dfs(z, x);
sp[tim++][0] = {dep[x], x};
}
};
dfs(0, 0);
for (int j = 1; (1 << j) <= tim; j++) {
for (int i = 0; i + (1 << j) - 1 < tim; i++) {
sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
vector<int> sz(n), rem(n);
function<void(int, int)> compute_subtree = [&](int x, int p) {
sz[x] = 1;
for (auto [z, c] : g[x]) {
if (z == p || rem[z]) continue;
compute_subtree(z, x);
sz[x] += sz[z];
}
};
auto get_centroid = [&](int x) {
compute_subtree(x, -1);
int tree_size = sz[x];
bool found = 0;
while (!found) {
found = 1;
for (auto [z, c] : g[x]) {
if (rem[z] || sz[z] > sz[x]) continue;
if (sz[z] > tree_size / 2) {
x = z;
found = 0;
}
}
}
return x;
};
function<int(int)> build_centroid_tree = [&](int x) {
x = get_centroid(x);
rem[x] = 1;
for (auto [z, c] : g[x]) {
if (rem[z]) continue;
z = build_centroid_tree(z);
par[z] = x;
}
return x;
};
int rt = build_centroid_tree(0);
par[rt] = -1;
}
int lca(int x, int y) {
x = tin[x]; y = tin[y];
if (x > y) swap(x, y);
int j = __lg(y - x + 1);
return min(sp[x][j], sp[y - (1 << j) + 1][j]).second;
}
long long dist(int x, int y) {
return d[x] + d[y] - 2 * d[lca(x, y)];
}
void update(int x) {
int z = x;
while (z != -1) {
ans[z] = min(ans[z], dist(z, x));
z = par[z];
}
}
long long query(int x) {
int z = x;
long long res = INFF;
while (z != -1) {
res = min(res, ans[z] + dist(z, x));
z = par[z];
}
return res;
}
void reset(int x) {
int z = x;
while (z != -1) {
ans[z] = INFF;
z = par[z];
}
}
long long Query(int s, int X[], int t, int Y[]) {
for (int i = 0; i < s; i++) {
update(X[i]);
}
long long ans = INFF;
for (int i = 0; i < t; i++) {
ans = min(ans, query(Y[i]));
}
for (int i = 0; i < s; i++) {
reset(x[i]);
}
return ans;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:15:9: error: 'a' was not declared in this scope
15 | g[a[i]].push_back({b[i], d[i]});
| ^
factories.cpp:15:26: error: 'b' was not declared in this scope
15 | g[a[i]].push_back({b[i], d[i]});
| ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:148:13: error: 'x' was not declared in this scope
148 | reset(x[i]);
| ^
