#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int MAX_N = 1 << 19;
vector <int> graph[MAX_N];
struct Edge {
int u, v, w;
Edge(int _u = 0, int _v = 0, int _w = 0):
u(_u), v(_v), w(_w) {}
int get_other(int x) const {
return x ^ u ^ v;
}
};
Edge edge[MAX_N];
lli pref_w[MAX_N];
int in[MAX_N], depth[MAX_N];
int timeDFS = 0;
int mn_depth[__lg(MAX_N) + 1][MAX_N << 1];
void DFS(int u) {
in[u] = ++timeDFS;
mn_depth[0][in[u]] = u;
for (int id : graph[u]) {
int v = edge[id].get_other(u);
if (in[v]) continue;
depth[v] = depth[u] + 1;
pref_w[v] = pref_w[u] + edge[id].w;
DFS(v);
mn_depth[0][++timeDFS] = u;
}
}
int Find_LCA(int u, int v) {
if (in[u] > in[v]) swap(u, v);
int k = __lg(in[v] - in[u] + 1);
int& x = mn_depth[k][in[u]]; int& y = mn_depth[k][in[v] - (1 << k) + 1];
return depth[x] < depth[y] ? x : y;
}
lli Path_Len(int u, int v) {
return pref_w[u] + pref_w[v] - 2 * pref_w[Find_LCA(u, v)];
}
int removed[MAX_N], cen_parent[MAX_N], sub_sz[MAX_N];
int Find_Centroid(int s, int sz) {
int last = s, parent = 0;
while (true) {
for (int id : graph[s]) {
int v = edge[id].get_other(s);
if (v == parent or removed[v]) continue;
if (sub_sz[v] * 2 > sz) {
last = v; break;
}
}
if (last == s) break;
parent = s; s = last;
}
return last;
}
int get_size(int u, int parent) {
sub_sz[u] = 1;
for (int id : graph[u]) {
int v = edge[id].get_other(u);
if (v == parent or removed[v]) continue;
sub_sz[u] += get_size(v, u);
}
return sub_sz[u];
}
int Build_Centroid(int s) {
int cen_node = Find_Centroid(s, get_size(s, 0));
removed[cen_node] = true;
for (int id : graph[cen_node]) {
int v = edge[id].get_other(cen_node);
if (removed[v]) continue;
int x = Build_Centroid(v);
cen_parent[x] = cen_node;
}
return cen_node;
}
lli min_path[MAX_N];
const lli inf = 0x3f3f3f3f3f3f3f3f;
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; ++i) {
A[i] += 1; B[i] += 1;
edge[i] = Edge(A[i], B[i], D[i]);
graph[A[i]].push_back(i);
graph[B[i]].push_back(i);
}
DFS(1);
for (int i = 1; i <= __lg(N) + 1; ++i) {
for (int u = 1; u + (1 << i) <= timeDFS + 1; ++u) {
int& x = mn_depth[i - 1][u]; int& y = mn_depth[i - 1][u + (1 << (i - 1))];
mn_depth[i][u] = depth[x] < depth[y] ? x : y;
}
}
Build_Centroid(1);
memset(min_path, 0x3f, sizeof min_path);
}
void minimise(lli& x, lli y) {
if (x > y) x = y;
}
void Update(int pos) {
int c = pos;
while (c) {
minimise(min_path[c], Path_Len(c, pos));
c = cen_parent[c];
}
}
lli Ask(int pos) {
lli ans = inf;
int c = pos;
while (c) {
minimise(ans, min_path[c] + Path_Len(c, pos));
c = cen_parent[c];
}
return ans;
}
void Clean(int pos) {
int c = pos;
while (c) {
min_path[c] = inf;
c = cen_parent[c];
}
}
lli Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++i) {
X[i] += 1;
Update(X[i]);
}
lli mn = inf;
for (int i = 0; i < T; ++i) {
Y[i] += 1;
minimise(mn, Ask(Y[i]));
}
for (int i = 0; i < S; ++i) {
Clean(X[i]);
}
return mn;
}
Compilation message
factories.cpp:146:5: error: ambiguating new declaration of 'lli Query(int, int*, int, int*)'
146 | lli Query(int S, int X[], int T, int Y[]) {
| ^~~~~
In file included from factories.cpp:1:
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[]);
| ^~~~~
