#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> s;
vector<int> dep, euler, pos, lg, sz, par, vis;
vector<ll> d2r, best;
void dfs(int x, int p) {
pos[x] = euler.size();
euler.push_back(x);
for (auto [y, z] : adj[x]) {
if (y == p) continue;
dep[y] = dep[x] + 1;
d2r[y] = d2r[x] + z;
dfs(y, x);
euler.push_back(x);
}
}
int f(int i, int j) {
return (i != -1 && (j == -1 || dep[i] < dep[j])) ? i : j;
}
void build() {
int n = euler.size();
s.resize(lg[n] + 1);
s[0] = euler;
for (int i = 0; i < lg[n]; i++) {
s[i + 1].resize(n - (2 << i) + 1);
for (int j = 0; j + (2 << i) <= n; j++) {
s[i + 1][j] = f(s[i][j], s[i][j + (1 << i)]);
}
}
}
int lca(int a, int b) {
a = pos[a], b = pos[b];
if (a > b) swap(a, b); b++;
int k = lg[b - a];
return f(s[k][a], s[k][b - (1 << k)]);
}
ll dis(int a, int b) {
return d2r[a] + d2r[b] - 2 * d2r[lca(a, b)];
}
void init(int x, int p) {
sz[x] = 1;
for (auto [y, z] : adj[x]) {
if (y == p || vis[y]) continue;
init(y, x);
sz[x] += sz[y];
}
}
int find(int x, int p, int n) {
for (auto [y, z] : adj[x]) {
if (y == p || vis[y]) continue;
if (sz[y] * 2 > n) return find(y, x, n);
}
return x;
}
int cd(int x) {
init(x, -1);
vis[x = find(x, -1, sz[x])] = 1;
for (auto [y, z] : adj[x]) {
if (!vis[y]) par[cd(y)] = x;
}
return x;
}
void Init(int n, int A[], int B[], int D[]) {
N = n;
sz.resize(N);
adj.resize(N);
dep.resize(N);
pos.resize(N);
d2r.resize(N);
vis.resize(N);
par.resize(N);
best.resize(N, 1e18);
lg.resize(2 * N);
for (int i = 2; i < 2 * N; i++) lg[i] = lg[i / 2] + 1;
for (int i = 0; i < N - 1; i++) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, -1);
build();
par[cd(0)] = -1;
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
for (int j = X[i]; j != -1; j = par[j]) {
best[j] = min(best[j], dis(j, X[i]));
}
}
ll ans = 1e18;
for (int i = 0; i < T; i++) {
for (int j = Y[i]; j != -1; j = par[j]) {
ans = min(ans, best[j] + dis(j, Y[i]));
}
}
for (int i = 0; i < S; i++) {
for (int j = X[i]; j != -1; j = par[j]) {
best[j] = 1e18;
}
}
return ans;
}
