#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> p, dep, euler, P, lg;
vector<int64_t> dis, best;
vector<vector<int>> st;
vector<vector<pair<int, int>>> adj;
constexpr int64_t inf = 1E18;
int F(int x, int y) {
return dep[x] < dep[y] ? x : y;
}
int lca(int x, int y) {
if (x == y) {
return x;
}
if (P[x] > P[y]) {
swap(x, y);
}
int z = lg[P[y] - P[x] + 1];
return F(st[P[x]][z], st[P[y] + 1 - (1 << z)][z]);
}
void Init(int n, int A[], int B[], int D[]) {
N = n;
p.resize(N);
P.resize(N);
dis.resize(N);
dep.resize(N);
adj.resize(N);
best.resize(N, inf);
lg.resize(2 * N + 1);
for (int i = 2; i <= 2 * N; i++) {
lg[i] = lg[i / 2] + 1;
}
st = vector(2 * N - 1, vector<int>(lg[2 * N - 1] + 1, -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]);
}
auto dfs = [&](auto dfs, int x, int p) -> void {
P[x] = euler.size();
euler.push_back(x);
for (auto [y, z] : adj[x]) {
if (y == p) {
continue;
}
dep[y] = dep[x] + 1;
dis[y] = dis[x] + z;
dfs(dfs, y, x);
euler.push_back(x);
}
};
dfs(dfs, 0, -1);
for (int i = 0; i < 2 * N - 1; i++) {
st[i][0] = euler[i];
}
for (int j = 0; j < lg[2 * N - 1]; j++) {
for (int i = 0; i + (2 << j) < 2 * N; i++) {
st[i][j + 1] = F(st[i][j], st[i + (1 << j)][j]);
}
}
vector<bool> vis(N);
vector<int> sz(N);
auto init = [&](auto init, int x, int p) -> void {
sz[x] = 1;
for (auto [y, _] : adj[x]) {
if (y == p || vis[y]) {
continue;
}
init(init, y, x);
sz[x] += sz[y];
}
};
auto find = [&](auto find, int x, int p, int s) -> int {
for (auto [y, _] : adj[x]) {
if (y == p || vis[y] || sz[y] * 2 <= s) {
continue;
}
return find(find, y, x, s);
}
return x;
};
auto cd = [&](auto cd, int x) -> int {
init(init, x, -1);
x = find(find, x, -1, sz[x]);
vis[x] = 1;
for (auto [y, _] : adj[x]) {
if (vis[y]) {
continue;
}
p[cd(cd, y)] = x;
}
return x;
};
p[cd(cd, 0)] = -1;
}
int64_t dist(int x, int y) {
return dis[x] + dis[y] - 2 * dis[lca(x, y)];
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int x = X[i];
while (x != -1) {
best[x] = min(best[x], dist(x, X[i]));
x = p[x];
}
}
auto ans = inf;
for (int i = 0; i < T; i++) {
int x = Y[i];
while (x != -1) {
ans = min(ans, best[x] + dist(x, Y[i]));
x = p[x];
}
}
for (int i = 0; i < S; i++) {
int x = X[i];
while (x != -1) {
best[x] = inf;
x = p[x];
}
}
return ans;
}
