#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>> adj[500001];
int hi[500001];
int P[500001][19];
long long sum[500001][19];
void dfs(int i,int pr,long long len){
hi[i] = hi[pr]+1;
P[i][0]= pr;
sum[i][0] =len;
for(int j = 1;j<19;j++){
P[i][j] = P[P[i][j-1]][j-1];
sum[i][j]= sum[i][j-1]+sum[P[i][j-1]][j-1];
}
for(auto j:adj[i]){
if(j.first!=pr){
dfs(j.first,i,j.second);
}
}
}long long lca(int x,int y){
long long su = 0;
if(hi[x]<hi[y]) swap(x,y);
for(int k=18;k>=0;k--)
{
if(hi[x]-(1<<k) >= hi[y]){
su+=sum[x][k];
x=P[x][k];
}
}
if(x==y) return su;
for(int k=18;k>=0;k--)
{
if(P[x][k] != P[y][k]){
su+=sum[x][k]+sum[y][k];
x=P[x][k],y=P[y][k];
}
}
return su+sum[x][0]+sum[y][0];
}
int sz[500001];
int vis[500001];
int par[500001];
long long best[500001];
int vi[500001];
int va = 1;
void upd(int i){
long long s = i;
int idx = 0;
while(s!=-1){
if(vi[s]!=va){
vi[s] =va;
best[s] = 1e18;
}
best[s] = min(best[s],dist[i][idx]);
s= par[s];
idx++;
}
}
vector<long long> dist[500001];
void computedist(int n){
for(int i = 0;i<n;i++){
for(int j = i;j!=-1;j=par[j]){
dist[i].push_back(lca(j,i));
}
}
}
long long ans(int i){
long long s = i , re = 1e18;
int idx = 0;
while(s!=-1){
if(vi[s]!=va){
vi[s] =va;
best[s] = 1e18;
}
re = min(re,best[s]+dist[i][idx]);
s= par[s];
idx++;
}
return re;
}
int find_size(int v, int p = -1) {
if(vis[v]) return 0;
sz[v] = 1;
for(auto x: adj[v]) {
if (x.first != p) {
sz[v] += find_size(x.first, v);
}
}
return sz[v];
}
int find_centroid(int v, int p, int n) {
for (auto x: adj[v]) {
if (x.first != p) {
if (!vis[x.first] && sz[x.first] > n / 2) {
return find_centroid(x.first, v, n);
}
}
}
return v;
}
void centroid(int v = 0, int p = -1) {
find_size(v);
int c = find_centroid(v,-1,sz[v]);
vis[c] = true;
par[c] = p;
for(auto x:adj[c]) {
if (!vis[x.first]) {
centroid(x.first, c);
}
}
}
void Init(int N,int A[],int B[],int D[]){
for(int i = 0;i<N-1;i++){
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
centroid();
dfs(0,0,0);
computedist(N);
}
long long Query(int S, int X[], int T,int Y[]) {
for(int i = 0;i<S;i++){
upd(X[i]);
}
long long Res = 1e18;
for(int i = 0;i<T;i++){
Res = min(Res,ans(Y[i]));
}
va++;
return Res;
}
Compilation message
factories.cpp: In function 'void upd(int)':
factories.cpp:58:31: error: 'dist' was not declared in this scope
58 | best[s] = min(best[s],dist[i][idx]);
| ^~~~
