//#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, lg[2 * M];
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 v, int l, int r, int i, long long k, bool g) {
if (l == r) {
seg[g][v] = k;
return;
}
int mid = (r + l) >> 1;
if (i <= mid) {
if (l == mid)
seg[g][v << 1] = k;
else
update(v << 1, l, mid, i, k, g);
}
else {
if (mid + 1 == r)
seg[g][v << 1 | 1] = k;
else
update(v << 1 | 1, mid + 1, r, i, k, g);
}
seg[g][v] = min(seg[g][v << 1], seg[g][v << 1 | 1]);
}
long long get(int v, int l, int r, bool g) {
if (ql <= l && r <= qr)
return seg[g][v];
if (r < ql || qr < l)
return 1e18 ;
int mid = (r + l) >> 1;
long long a = 1e18, b = 1e18;
if (ql <= l && mid <= qr)
a = seg[g][v << 1];
else if (mid < ql || qr < l)
a = a;
else
a = get(v << 1, l, mid, g);
if (ql <= mid + 1 && r <= qr)
b = seg[g][v << 1 | 1];
else if (r < ql || qr < mid + 1)
b = b;
else
b = get(v << 1 | 1, mid + 1, r, g);
return min(a, b);
}
void rem(int v, int l, int r, int i, bool g) {
seg[g][v] = 1e18 ;
if (l == r)
return;
int mid = (r + l) >> 1;
if (i <= mid) {
if (l == mid) {
seg[g][v << 1] = 1e18;
return;
}
rem(v << 1, l, mid, i, g);
}
else {
if (mid + 1 == r) {
seg[g][v << 1 | 1] = 1e18;
return;
}
rem(v << 1 | 1, mid + 1, r, i, g);
}
}
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);
for (int i = 2; i < 2 * n; i++)
lg[i] = lg[i / 2] + 1;
queue<pair<int, pair<int, int>>> q;
q.push({1, {0, n - 1}});
while (q.size()) {
int v = q.front().first, l = q.front().second.first, r = q.front().second.second;
seg[0][v] = seg[1][v] = 1e18;
q.pop();
if (l != r) {
int mid = (l + r) >> 1;
q.push({v << 1, {l, mid}});
q.push({v << 1 | 1, {mid + 1, r}});
}
}
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(1, 0, n - 1, st[X[i]], dis[X[i]], 0);
sv.push_back({st[X[i]], X[i]});
}
for (int i = 0; i < T; i++) {
update(1, 0, n - 1, 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(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (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(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (2ll * dis[v]);
ans = min(ans, f);
}
}
for (int i = 0; i < S; i++)
rem(1, 0, n - 1, st[X[i]], 0);
for (int i = 0; i < T; i++)
rem(1, 0, n - 1, st[Y[i]], 1);
return ans;
}
