#include <iostream>
#include <vector>
#include <algorithm>
#include "factories.h"
using namespace std;
using ll = long long;
const int maxn = 5e5 + 1;
vector <pair <int, int>> adj[maxn];
int anc[maxn][20];
bool blocked[maxn];
int sz[maxn], visit[maxn], finish[maxn];
ll depth[maxn];
vector <int> centroids[maxn];
ll dis[maxn];
int get_subtree_sz(int s, int p) {
sz[s] = 1;
for (auto i : adj[s]) {
if (blocked[i.first] || i.first == p)
continue;
sz[s] += get_subtree_sz(i.first, s);
}
return sz[s];
}
int get_centroid(int s, int p, int st_sz) {
for (auto i : adj[s]) {
if (i.first == p || blocked[i.first])
continue;
if (sz[i.first] * 2 > st_sz)
return get_centroid(i.first, s, st_sz);
}
return s;
}
void add_centroid(int s, int p, int centroid) {
centroids[s].push_back(centroid);
for (auto i : adj[s]) {
if (i.first == p || blocked[i.first])
continue;
add_centroid(i.first, s, centroid);
}
}
void dfs(int s) {
int centroid = get_centroid(s, s, get_subtree_sz(s, s));
blocked[centroid] = true;
add_centroid(centroid, centroid, centroid);
for (auto i : adj[centroid]) {
if (blocked[i.first])
continue;
dfs(i.first);
}
}
int t = 0;
void dfs2(int s, int p) {
anc[s][0] = p;
visit[s] = t++;
for (int i = 1; i < 20; i++)
anc[s][i] = anc[anc[s][i-1]][i-1];
for (auto i : adj[s]) {
if (i.first == p)
continue;
depth[i.first] = depth[s] + i.second;
dfs2(i.first, s);
}
finish[s] = t++;
}
bool is_ancestor(int a, int b) {
return visit[a] <= visit[b] && finish[a] >= finish[b];
}
int get_lca(int a, int b) {
if (is_ancestor(a, b))
return a;
if (is_ancestor(b, a))
return b;
int lca = a;
for (int i = 19; i >= 0; i--) {
if (!is_ancestor(anc[lca][i], b))
lca = anc[lca][i];
}
return anc[lca][0];
}
void update_dis(int s) {
for (auto centroid : centroids[s]) {
int lca = get_lca(centroid, s);
dis[centroid] = min(dis[centroid], depth[centroid] + depth[s] - 2 * depth[lca]);
}
}
ll get_ans(int s) {
ll ans = 1e16;
for (auto centroid : centroids[s]) {
int lca = get_lca(centroid, s);
ans = min(ans, dis[centroid] + depth[centroid] + depth[s] - 2 * depth[lca]);
}
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; i++) {
A[i]++;
B[i]++;
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(1);
dfs2(1, 1);
fill(dis, dis + maxn, 1e16)
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
update_dis(X[i]+1);
}
ll ans = 1e16;
for (int i = 0; i < T; i++) {
ll tp = get_ans(Y[i] + 1);
ans = min(ans, tp);
}
// reiinitilise dis array so we don't have to reset all the values
for (int i = 0; i < S; i++)
dis[X[i] + 1] = 1e16;
return ans;
}
// int main() {
// int N, q;
// cin >> N >> q;
// int A[maxn], B[maxn], D[maxn];
// for (int i = 0; i < N-1; i++)
// cin >> A[i] >> B[i] >> D[i];
// Init(N, A, B, D);
// while (q--) {
// int S, T;
// cin >> S >> T;
// int X[maxn], Y[maxn];
// for (int i = 0; i < S; i++)
// cin >> X[i];
// for (int i = 0; i < T; i++)
// cin >> Y[i];
// cout << Query(S, X, T, Y) << '\n';
// }
// }
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:103:32: error: expected ';' before '}' token
103 | fill(dis, dis + maxn, 1e16)
| ^
| ;
104 | }
| ~
