#include <bits/stdc++.h>
using namespace std;
#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
const int N = 5e5 + 5;
const int LG = 20;
const ll inf = 1e18;
int n, timer, tour;
int tin[N], tout[N], yes[N], hi[N];
int ri[N], st[N * 2][21];
ll val[N], dp[N][2];
vector<int> vec;
vector<pair<int, int>> adj[N], g[N];
bool cmp(int u, int v) {
return tin[u] < tin[v];
}
bool inside(int u, int v) {
return tin[u] <= tin[v] && tin[v] <= tout[u];
}
int lca(int u, int v) {
int l = ri[u], r = ri[v];
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
u = st[l][k];
v = st[r - MASK(k) + 1][k];
return (hi[u] < hi[v] ? u : v);
}
void init(int u, int par) {
tin[u] = ++timer;
st[++tour][0] = u;
ri[u] = tour;
hi[u] = hi[par] + 1;
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
if (v == par) continue;
val[v] = val[u] + w;
init(v, u);
st[++tour][0] = u;
}
tout[u] = timer;
}
void dfs(int u, int par) {
for (auto it : g[u]) {
int v = it.fi, w = it.se;
if (v == par) continue;
dfs(v, u);
dp[u][0] = min(dp[u][0], dp[v][0] + w);
}
if (yes[u] == 2) {
dp[u][0] = 0;
}
}
void reroot(int u, int par) {
ll mn = dp[u][1];
if (yes[u] == 2) mn = 0;
for (int i = g[u].size() - 1; i >= 0; i--) {
int v = g[u][i].fi, w = g[u][i].se;
if (v == par) continue;
dp[v][1] = min(dp[v][1], mn + w);
mn = min(mn, dp[v][0] + w);
}
mn = inf;
for (auto it : g[u]) {
int v = it.fi, w = it.se;
if (v == par) continue;
dp[v][1] = min(dp[v][1], mn + w);
reroot(v, u);
mn = min(mn, dp[v][0] + w);
}
}
void build_virtual_tree() {
sort(all(vec), cmp);
vec.erase(unique(all(vec)), vec.end());
int cur = vec.size();
for (int i = 1; i < cur; i++) {
vec.pb(lca(vec[i - 1], vec[i]));
}
sort(all(vec), cmp);
vec.erase(unique(all(vec)), vec.end());
stack<int> st;
st.push(vec[0]);
for (int i = 1; i < (int)vec.size(); i++) {
while (!inside(st.top(), vec[i])) {
st.pop();
}
int u = st.top();
int v = vec[i];
g[u].pb({v, val[v] - val[u]});
g[v].pb({u, val[v] - val[u]});
st.push(vec[i]);
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i <= n - 2; i++) {
int u = A[i], v = B[i], d = D[i];
u++, v++;
adj[u].pb({v, d});
adj[v].pb({u, d});
}
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = inf;
}
init(1, 0);
for (int j = 1; j <= LG; j++) {
for (int i = 1; i + MASK(j) - 1 <= tour; i++) {
int u = st[i][j - 1];
int v = st[i + MASK(j - 1)][j - 1];
st[i][j] = (hi[u] < hi[v] ? u : v);
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
X[i]++;
yes[X[i]] = 1;
vec.pb(X[i]);
}
for (int i = 0; i < T; i++) {
Y[i]++;
yes[Y[i]] = 2;
vec.pb(Y[i]);
}
build_virtual_tree();
dfs(vec[0], 0);
reroot(vec[0], 0);
ll ans = inf;
for (int x : vec) {
if (yes[x] == 1) {
ans = min({ans, dp[x][0], dp[x][1]});
}
yes[x] = 0;
dp[x][0] = dp[x][1] = inf;
g[x].clear();
}
vec.clear();
return ans;
}
