#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 22, M = 2 * N + 5;
std::vector<std::pair<int, i64>> e[N];
std::pair<int, int> st[M][K + 1];
int lg[M + 1];
int n, P[N];
i64 D[N];
int timer = 0;
std::pair<int, int> pos[M];
void dfs(int u, int p, i64 d = 0, int d1 = 0){
P[u] = timer;
pos[timer++] = {d1, u};
D[u] = d;
for (auto [v, w] : e[u]) {
if (v != p) {
dfs(v, u, d + w, d1 + 1);
pos[timer++] = {d1, u};
}
}
}
inline std::pair<int, int> range(int L, int R) {
if (L > R) std::swap(L, R);
int j = lg[R - L + 1];
auto minimum = std::min(st[L][j], st[R - (1 << j) + 1][j]);
return minimum;
}
inline int lca(int u, int v) {
return range(P[u], P[v]).second;
}
i64 dist(int u, int v) {
return D[u] + D[v] - 2 * D[lca(u, v)];
}
void Init(int n, int A[], int B[], int D[]) {
lg[1] = 0;
for (int i = 2; i <= M; i++)
lg[i] = lg[i / 2] + 1;
::n = n;
for (int i = 0; i < n - 1; i++) {
e[A[i]].emplace_back(B[i], D[i]);
e[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, 0);
for (int i = 0; i < M; i++)
st[i][0] = pos[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= M; i++)
st[i][j] = std::min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
long long Query(int S, int X[], int T, int Y[]) {
if (S + T <= 1000) {
i64 ans = 1e16;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = std::min(ans, dist(X[i], Y[j]));
}
}
return ans;
}
std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> q;
std::vector<i64> dist(n, 1e16);
for (int i = 0; i < S; i++) {
q.emplace(0, X[i]);
dist[X[i]] = 0;
}
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (d > dist[u]) {
continue;
}
for (auto [v, w] : e[u]) {
if (dist[v] > d + w) {
dist[v] = d + w;
q.emplace(dist[v], v);
}
}
}
i64 ans = 1e16;
for (int i = 0; i < T; i++) {
ans = std::min(ans, dist[Y[i]]);
}
return ans;
}
