#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MXN = 500000;
const int LOG = 20;
const int64_t INF = 1e18;
vector<array<int, 2>> g[MXN];
int sz[MXN], centroid[MXN], up[LOG][MXN], tin[MXN], tout[MXN];
int64_t depth[MXN], best[MXN];
vector<bool> vis(MXN, 0);
int timer = 0;
void dfs(int node, int par, int dist){
tin[node] = timer++;
depth[node] = depth[par] + int64_t(dist);
up[0][node] = par;
for(int i = 1; i < LOG; i++)
up[i][node] = up[i-1][up[i-1][node]];
for(auto& [v, d] : g[node]){
if(v == par)
continue;
dfs(v, node, d);
sz[node] += sz[v];
}
tout[node] = timer;
}
inline bool isAncestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(isAncestor(u, v))
return u;
if(isAncestor(v, u))
return v;
for(int i = LOG-1; i >= 0; --i){
if(!isAncestor(up[i][u], v))
u = up[i][u];
}
return up[0][u];
}
inline int64_t dist(int u, int v){
return depth[u] + depth[v] - 2*depth[lca(u, v)];
}
void decompose(int node, int c){
int inv = -1, szl = (sz[node] >> 1);
for(auto& [v, d] : g[node]){
if(!vis[v] && sz[v] > szl){
inv = v;
break;
}
}
if(inv != -1){
sz[node] -= sz[inv];
sz[inv] += sz[node];
return decompose(inv, c);
}
vis[p] = 1;
centroid[p] = c;
for(auto& [v, d] : g[node]){
if(!vis[v]){
centroid[v] = p;
decompose(v, p);
}
}
}
vector<int> hit;
void update(int node){
int v = node;
while(v != -1){
best[v] = min(best[v], dist(node, v));
hit.push_back(v);
v = centroid[v];
}
}
int64_t query(int node){
int64_t ans = INF;
int v = node;
while(v != -1){
ans = min(ans, best[v] + dist(v, node));
}
return ans;
}
void Init(int n, int A[], int B[], int D[]){
for(int i = 0; i < n; i++)
best[i] = INF;
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]});
}
dfs(0, 0, 0);
decompose(0, -1);
}
long long Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i++)
update(X[i]);
int64_t ans = INF;
for(int i = 0; i < T; i++)
ans = min(ans, query(Y[i]));
for(int i : hit)
best[i] = INF;
hit.clear();
return ans;
}
Compilation message
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:72:6: error: 'p' was not declared in this scope
72 | vis[p] = 1;
| ^
