#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
class SparseTable {
vector<vector<ii>> st;
vector<ll> log; vector<ii> raw;
int n;
void computeLog() {
log.resize(n+1, -1);
int p = 0, two_pow = 1;
while (two_pow <= n) {
log[two_pow] = p++;
two_pow *= 2;
}
int prev = 0;
for_(i, 1, n+1) {
if (log[i] != -1) prev = log[i];
else log[i] = prev;
}
}
void buildTable() {
int k = log[n]+1;
st.resize(n, vector<ii> (k));
for_(i, 0, n) st[i][0] = raw[i];
for_(p, 1, k+1) for_(i, 0, n - (1<<p) + 1)
st[i][p] = min(st[i][p-1], st[i + (1 << (p-1))][p-1]);
}
public:
void build(vector<ii> nums) {
raw = nums;
n = nums.size();
computeLog();
buildTable();
}
int mn(int l, int r) {
int p = log[r-l+1];
return min(st[l][p], st[r - (1<<p) + 1][p]).second;
}
};
int n;
vector<vector<pair<int, ll>>> adjList;
vi removed, subtreeSize, centroid, tin, depth;
vector<ll> rootDist, whiteDist;
vector<ii> tour;
SparseTable st;
ll INF = 1e15;
int dfs(int p, int parent) {
int s = 1;
tin[p] = tour.size();
tour.push_back({depth[p], p});
for (auto i: adjList[p]) if (i.first != parent) {
rootDist[i.first] = rootDist[p]+i.second;
depth[i.first] = depth[p]+1;
s += dfs(i.first, p);
tour.push_back({depth[p], p});
}
subtreeSize[p] = s;
return s;
}
int lca(int u, int v) {
return st.mn(min(tin[u], tin[v]), max(tin[u], tin[v]));
}
ll dist(int u, int v) {
int lc = lca(u, v);
return rootDist[u] + rootDist[v] - 2*rootDist[lc];
}
void decompose(int p, int c) {
int invalidChild = -1, sizeLimit = (subtreeSize[p] >> 1);
for (auto i: adjList[p]) if (!removed[i.first] and subtreeSize[i.first] > sizeLimit) {
invalidChild = i.first;
break;
}
if (invalidChild != -1) {
subtreeSize[p] -= subtreeSize[invalidChild];
subtreeSize[invalidChild] += subtreeSize[p];
return decompose(invalidChild, c);
}
removed[p] = true;
centroid[p] = c;
for (auto i: adjList[p]) if (!removed[i.first]) {
centroid[i.first] = p;
decompose(i.first, p);
}
}
vi updated;
void update(int p) {
int v = p;
while (v != -1) {
ll d = dist(p, v);
whiteDist[v] = min(whiteDist[v], d);
updated.push_back(v);
v = centroid[v];
}
}
ll ans(int p) {
ll val = INF;
int v = p;
while (v != -1) {
val = min(val, whiteDist[v] + dist(p, v));
v = centroid[v];
}
return (val == 1e9 ? -1 : val);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
adjList.resize(n); subtreeSize.resize(n); removed.resize(n); centroid.resize(n, -1); depth.resize(n); tin.resize(n); rootDist.resize(n); whiteDist.resize(n, INF);
for_(i, 0, n-1) {
int a = A[i], b = B[i]; ll w = D[i];
adjList[a].push_back({b, w});
adjList[b].push_back({a, w});
}
dfs(0, 0);
decompose(0, -1);
st.build(tour);
}
ll Query(int S, int X[], int T, int Y[]) {
updated.clear();
for_(i, 0, S) update(X[i]);
ll val = INF;
for_(i, 0, T) val = min(val, ans(Y[i]));
for (int i: updated) whiteDist[i] = INF;
return val;
}
//int main() {
//#ifndef ONLINE_JUDGE
//freopen("test.in", "r", stdin);
//#endif
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//int N, q; cin >> N >> q;
//int A[100], B[100], D[100];
//for_(i, 0, N-1) {
//int a, b, w; cin >> a >> b >> w;
//A[i] = a; B[i] = b; D[i] = w;
//}
//Init(N, A, B, D);
//int X[100], Y[100];
//while (q--) {
//int S, T; cin >> S >> T;
//for_(i, 0, S) cin >> X[i];
//for_(i, 0, T) cin >> Y[i];
//cout << Query(S, X, T, Y) << endl;
//}
//return 0;
}
Compilation message
factories.cpp:181:1: error: expected declaration before '}' token
181 | }
| ^
