#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<vector<array<int, 2>>> g;
const int N = 500000;
const int LOG = 20;
const int64_t INF = 1e18;
struct LCA{
int tin[N], tout[N], up[LOG][N];
int64_t depth[N];
int timer = 0;
void init(){
dfs();
}
void dfs(int node = 0, int par = 0, int d = 0){
depth[node] = depth[par] + int64_t(d);
tin[node] = timer++;
up[0][node] = par;
for(int i = 1; i < LOG; i++)
up[i][node] = up[i-1][up[i-1][node]];
for(auto& [v, dx] : g[node]){
if(v == par)
continue;
dfs(v, node, dx);
}
tout[node] = timer;
}
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];
}
int64_t dist(int u, int v){
return depth[u] + depth[v] - 2*depth[lca(u, v)];
}
};
struct CentroidDecomposition{
bool vis[N];
vector<int> hit;
int sz[N], par[N];
int64_t best[N];
LCA S;
void init(int s, int A[], int B[], int D[]){
memset(sz, 0, sizeof sz);
memset(par, 0, sizeof par);
for(int i = 0; i < s; i++)
best[i] = INF;
for(int i = 0; i < s-1; i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
S.init();
tree();
}
int find(int node, int p = -1){
if(vis[node]) return 0;
sz[node] = 1;
for(auto& [v, d] : g[node]){
if(v != p)
sz[node] += find(v, node);
}
return sz[node];
}
int centroid(int node, int p, int n){
for(auto& [v, d] : g[node]){
if(v == p)
continue;
if(!vis[v] && sz[v] > n / 2)
return centroid(v, node, n);
}
return node;
}
void tree(int node = 0, int p = -1){
find(node);
int c = centroid(node, -1, sz[node]);
vis[c] = true;
par[c] = p;
for(auto& [v, d] : g[c]){
if(!vis[v])
tree(v, c);
}
}
void update(int node){
int u = node;
while(u != -1){
best[u] = min(best[u], S.dist(u, node));
hit.push_back(u);
u = par[u];
}
}
int64_t query(int node){
int64_t ans = INF;
int u = node;
while(u != -1){
ans = min(ans, best[u] + S.dist(u, node));
u = par[u];
}
return ans;
}
void reset(){
for(int i : hit)
best[i] = INF;
}
}D;
void Init(int n, int A[], int B[], int d[]){
D.init(n, A, B, d);
}
int64_t Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i++)
D.update(X[i]);
int64_t ans = INF;
for(int i = 0; i < T; i++)
ans = min(ans, D.query(Y[i]));
D.reset();
return ans;
}
Compilation message
factories.cpp:146:9: error: ambiguating new declaration of 'int64_t Query(int, int*, int, int*)'
146 | int64_t Query(int S, int X[], int T, int Y[]){
| ^~~~~
In file included from factories.cpp:2:
factories.h:5:11: note: old declaration 'long long int Query(int, int*, int, int*)'
5 | long long Query(int S, int X[], int T, int Y[]);
| ^~~~~
