#include <bits/stdc++.h>
#include <factories.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long ans, spt[N][L], dis[N];
vector<pair<int, int>> adj[N];
void dfs(int v, int p) {
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i].first, w = adj[v][i].second;
if (u == p) {
swap(adj[v].back(), adj[v][i]);
adj[v].pop_back();
if (i == adj[v][i].size())
return;
u = adj[v][i].first, w = adj[v][i].second;
}
par[u][0] = v;
spt[u][0] = w;
h[u] = h[v] + 1;
dfs(u, v);
}
}
void dfsu(int v, int p) {
for (auto [u, w]: adj[v]) {
dfsu(u, v);
dis[v] = min(dis[v], dis[u] + w);
}
}
void dfsd(int v, int p) {
for (auto [u, w]: adj[v]) {
dis[u] = min(dis[u], dis[v] + w);
dfsd(u, v);
}
}
long long distance(int v, int u) {
long long res = 0;
if (h[v] < h[u]) swap(v, u);
for (int i = 0; i < L && res < ans; i++)
if ((1 << i) & (h[v] - h[u])) {
res += spt[v][i];
v = par[v][i];
}
if (v == u) return res;
for (int i = L - 1; i >= 0 && res < ans; i--)
if (par[v][i] != par[u][i]) {
res += spt[v][i] + spt[u][i];
v = par[v][i];
u = par[u][i];
}
return res + spt[v][0] + spt[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i] + 1].push_back({B[i] + 1, D[i]});
adj[B[i] + 1].push_back({A[i] + 1, D[i]});
}
dfs(1, 0);
for (int i = 1; i < L; i++)
for (int j = 1; j <= n; j++) {
par[j][i] = par[par[j][i - 1]][i - 1];
spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
}
}
long long Query(int S, int X[], int T, int Y[]) {
ans = I;
if (S < Q) {
for (int i = 0; i < T; i++)
for (int j = 0; j < S; j++)
ans = min(ans, distance(Y[i] + 1, X[j] + 1));
return ans;
}
for (int i = 0; i < N; dis[i++] = I);
for (int i = 0; i < S; dis[X[i++] + 1] = 0);
dfsu(1, 0);
dfsd(1, 0);
for (int i = 0; i < T; i++)
ans = min(ans, dis[Y[i] + 1]);
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for (int i = 0; i < adj[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~
factories.cpp:18:23: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'size'
18 | if (i == adj[v][i].size())
| ^~~~
