#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long st[500001], fn[500001], dis[500001], par[20][500001], t = 0, n, seg[2000001][2], h[500001], ans;
vector<pair<int, long long>> adj[500001];
void dfs( long long v, long long p, long long d1, long long h1) {
dis[v] = d1;
h[v] = h1;
st[v] = t++;
par[0][v] = p;
for ( long long i = 1; i < 20; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
for (auto u : adj[v])
if (u.first != p)
dfs(u.first, v, d1 + 1ll * u.second, h1 + 1);
fn[v] = t - 1;
// cout << v << " " << st[v] << " " << fn[v] << endl;
return;
}
long long getp(long long v, long long k) {
for (long long i = 20 - 1; ~i; i--)
if ((k >> i) & 1)
v = par[i][v];
return v;
}
long long lca(long long v, long long u) {
if (h[v] < h[u])
swap(v, u);
v = getp(v, h[v] - h[u]);
if (v == u)
return v;
for (long long i = 20 - 1 ; ~i; i--)
if (par[i][v] != par[i][u]) {
v = par[i][v];
u = par[i][u];
}
return par[0][v];
}
void update(int v, int l, int r, long long i, long long k, bool g) {
// cout << v << "A" << endl;
if (l == r) {
seg[v][g] = k;
return;
}
long long mid = (r + l) / 2;
(i <= mid) ? update(v * 2, l, mid, i, k, g) : update(v * 2 + 1, mid + 1, r, i, k, g);
seg[v][g] = min(seg[v * 2][g], seg[v * 2 + 1][g]);
}
long long get(int v, int l, int r, long long ql, long long qr, bool g) {
// cout << "a" << seg[v][g] << " " << l << " " << r << " " << ql << " " << qr << endl;
if (ql <= l && r <= qr)
return seg[v][g];
if (r < ql || qr < l)
return 1e18 ;
long long mid = (r + l) / 2;
return min(get(v * 2, l, mid, ql, qr, g), get(v * 2 + 1, mid + 1, r, ql, qr, g));
}
void rem(int v, int l, int r, long long i, bool g) {
// cout << v << "C" << endl;
seg[v][g] = 1e18 ;
if (l == r)
return;
long long mid = (r + l) / 2;
(i <= mid) ? rem(v * 2, l, mid, i, g) : rem(v * 2 + 1, mid + 1, r, i, g);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (long long 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);
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[v][0] = seg[v][1] = 1e18 ;
q.pop();
// cout << v << endl;
if (l != r) {
int mid = (l + r) / 2;
q.push({v * 2, {l, mid}});
q.push({v * 2 + 1, {mid + 1, r}});
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<pair<int, int>> sv;
for (long long 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 (long long 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());
ans = 1e18 ;
for (long long i = 0; i < int32_t(sv.size()); i++) {
long long v = sv[i].second;
long long f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2ll * dis[v]);
// cout << f << endl;
// cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
ans = min(ans, f);
if (i < int32_t(sv.size()) - 1) {
v = lca(sv[i].second, sv[i + 1].second);
f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2ll * dis[v]);
ans = min(ans, f);
// cout << f << endl;
// cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
// cout << v<< endl;
}
}
for (long long i = 0; i < S; i++)
rem(1, 0, n - 1, st[X[i]], 0);
for (long long i = 0; i < T; i++)
rem(1, 0, n - 1, st[Y[i]], 1);
return ans;
}
