//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 1;
int st[M], fn[M], t, cnt, n , loc[M], ql, qr , TV = 1;
vector<pair<int, long long>> adj[M];
long long dis[M], seg[2][M << 2];
pair<int, int> par[20][M << 1];
void dfs(int v, int p, long long d1, int h) {
dis[v] = d1;
st[v] = t++;
loc[v] = cnt;
par[0][cnt++] = {h, v};
for (auto u : adj[v])
if (u.first != p) {
dfs(u.first, v, d1 + 1ll * u.second, h + 1);
par[0][cnt++] = {h, v};
}
fn[v] = t - 1;
return;
}
void update(int i, long long k, bool g) {
i = i + TV;
seg[g][i] = k;
i /= 2;
while (i) {
seg[g][i] = min(seg[g][i << 1], seg[g][i << 1 | 1]);
i /= 2;
}
}
long long get(bool g) {
ql = ql + TV;
qr = qr + 1 + TV;
long long ret = 1e18;
while (ql < qr) {
if (ql & 1)
ret = min(ret, seg[g][ql++]);
if (qr & 1)
ret = min(ret, seg[g][--qr]);
ql /= 2;
qr /= 2;
}
return ret;
}
void rem(int i, bool g) {
i = i + TV;
seg[g][i] = 1e18;
i /= 2;
while (i) {
seg[g][i] = 1e18;
i /= 2;
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
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, 0, 0, 0);
while (TV < N)
TV *= 2;
for (int i = 0; i < 2 * TV; i++)
seg[0][i] = seg[1][i] = 1e18;
for (int i = 1; i < 20; i++)
for (int j = 0; j + (1 << i) < 2 * n; j++)
par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<pair<int, int>> sv;
for (int i = 0; i < S; i++) {
update(st[X[i]], dis[X[i]], 0);
sv.push_back({st[X[i]], X[i]});
}
for (int i = 0; i < T; i++) {
update(st[Y[i]], dis[Y[i]], 1);
sv.push_back({st[Y[i]], Y[i]});
}
sort(sv.begin(), sv.end());
long long ans = 1e18 ;
for (int i = 0; i < int(sv.size()); i++) {
int v = sv[i].second;
ql = st[v];
qr = fn[v];
long long f = get(0);
ql = st[v];
qr = fn[v];
f += get(1);
f -= (2ll * dis[v]);
ans = min(ans, f);
if (i < int(sv.size()) - 1) {
int vv = sv[i].second, uu = sv[i + 1].second;
if (loc[vv] > loc[uu])
swap(vv, uu);
int SV = loc[vv], SU = loc[uu], LG = __lg(SU - SV + 1);
pair<int, int> lca = min(par[LG][SV], par[LG][SU - (1 << LG) + 1]);
v = lca.second;
ql = st[v];
qr = fn[v];
f = get(0);
ql = st[v];
qr = fn[v];
f += get(1);
f -= (2ll * dis[v]);
ans = min(ans, f);
}
}
for (int i = 0; i < S; i++)
rem(st[X[i]], 0);
for (int i = 0; i < T; i++)
rem(st[Y[i]], 1);
return ans;
}
