#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
vector<ll> len, best;
vector<int> p, sz, vis, dep;
vector<vector<int>> par;
vector<vector<array<int, 2>>> adj;
void dfs(int x, int p) {
for (int i = 0; i < 18 && par[x][i] != -1; i++) {
par[x][i + 1] = par[par[x][i]][i];
}
for (auto [y, z] : adj[x]) {
if (y == p) continue;
par[y][0] = x;
dep[y] = dep[x] + 1;
len[y] = len[x] + z;
dfs(y, x);
}
}
void init(int x, int p) {
sz[x] = 1;
for (auto [y, z] : adj[x]) {
if (vis[y] || y == p) continue;
init(y, x);
sz[x] += sz[y];
}
}
int find(int x, int p, int s) {
for (auto [y, z] : adj[x]) {
if (vis[y] || y == p) continue;
if (sz[y] * 2 > s) return find(y, x, s);
}
return x;
}
int cd(int x) {
init(x, -1);
x = find(x, -1, sz[x]);
vis[x] = 1;
for (auto [y, z] : adj[x]) {
if (!vis[y]) {
p[cd(y)] = x;
}
}
return x;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 0; i < 19; i++) {
if ((dep[x] - dep[y]) >> i & 1) {
x = par[x][i];
}
}
if (x == y) return x;
for (int i = 18; i >= 0; i--) {
if (par[x][i] != par[y][i]) {
x = par[x][i];
y = par[y][i];
}
}
return par[x][0];
}
ll dis(int x, int y) {
return len[x] + len[y] - 2 * len[lca(x, y)];
}
void Init(int n, int A[], int B[], int D[]) {
N = n;
p.resize(N, -1);
sz.resize(N);
vis.resize(N);
adj.resize(N);
dep.resize(N);
len.resize(N);
par.resize(N, vector<int>(19, -1));
best.resize(N, 1e18);
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, -1);
cd(0);
}
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 = p[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 = p[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 = p[j]) {
best[j] = 1e18;
}
}
return ans;
}
