#include "factories.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = (int)5e5 + 7;
struct fen {
int tree[maxn];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val) {
while(pos < maxn) {
tree[pos] += val;
pos = pos | pos + 1;
}
}
int get(int r) {
int res = 0;
while (r >= 0) {
res += tree[r];
r = (r & r + 1) - 1;
}
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
fen tr1, tr2;
int tiktak;
int tin[maxn], tout[maxn];
int lc[20][maxn];
ll h[maxn];
vector<pair<int, int>> gr[maxn];
void dfs(int v, int pr) {
tin[v] = ++tiktak;
lc[0][v] = pr;
for (int i = 1; i < 20; i++) {
lc[i][v] = lc[i - 1][lc[i - 1][v]];
}
for (auto id : gr[v]) {
int to = id.first;
int w = id.second;
if (to == pr) continue;
h[to] = h[v] + w;
dfs(to, v);
}
tout[v] = tiktak;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 19; i >= 0; i--) {
if (!upper(lc[i][a], b)) a = lc[i][a];
}
return lc[0][a];
}
ll dist(int a, int b) {
return h[a] + h[b] - 2 * h[lca(a, b)];
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
gr[A[i]].push_back({B[i], D[i]});
gr[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = 1e18;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = min(ans, dist(X[i], Y[j]));
}
}
return ans;
}
