#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
const ll N = 5e5 + 5, K = 20;
ll n, in[N], ou[N], ti, up[K][N], d[N], u1[N], u2[N], dp[N][2];
vector<pair<ll, ll>> g[N], g1[N];
bool cmp(ll x, ll y) {
return in[x] < in[y];
}
bool is_p(ll u, ll v) {
return in[u] <= in[v] && ou[u] >= ou[v];
}
ll lca(ll u, ll v) {
if (u == v) return u;
if (in[u] > in[v]) swap(u, v);
for (ll i = K - 1; i >= 0; i--) if (!is_p(up[i][v], u)) v = up[i][v];
return up[0][v];
}
void dfs(ll v, ll p) {
in[v] = ti++;
up[0][v] = p;
for (ll i = 1; i < K; i++) up[i][v] = up[i - 1][up[i - 1][v]];
for (auto [x, w]: g[v]) {
if (x == p) continue;
d[x] = d[v] + w;
dfs(x, v);
}
ou[v] = ti;
}
void Init(int _n, int A[], int B[], int D[]) {
n = _n;
for (ll i = 0; i < n - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
}
void build(vll s) {
vll st;
for (auto x: s) {
while (st.size() && !is_p(st.back(), x)) st.pop_back();
if (st.size()) g1[st.back()].push_back({x, d[x] - d[st.back()]});
st.push_back(x);
}
}
void go(ll v) {
dp[v][0] = dp[v][1] = 1e18;
if (u1[v]) dp[v][0] = 0;
if (u2[v]) dp[v][1] = 0;
for (auto [x, w]: g1[v]) {
go(x);
dp[v][0] = min(dp[v][0], dp[x][0] + w);
dp[v][1] = min(dp[v][1], dp[x][1] + w);
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<ll> s;
for (ll i = 0; i < S; i++) s.push_back(X[i]);
for (ll i = 0; i < T; i++) s.push_back(Y[i]);
sort(s.begin(), s.end(), cmp);
for (ll i = 0; i < S + T - 1; i++) s.push_back(lca(s[i], s[i + 1]));
sort(s.begin(), s.end(), cmp);
s.resize(unique(s.begin(), s.end()) - s.begin());
build(s);
for (auto x: s) u1[x] = u2[x] = 0;
for (ll i = 0; i < S; i++) u1[X[i]] = 1;
for (ll i = 0; i < T; i++) u2[Y[i]] = 1;
go(s[0]);
ll ans = 1e18;
for (auto x: s) ans = min(ans, dp[x][0] + dp[x][1]);
for (auto x: s) g1[x].clear();
return ans;
}
