#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 5e5 + 10;
int M[N], from[N], to[N], w[N], P[20][N], H[N], St[N], Ft[N], n, tim; vector<int> adj[N]; ll S[N], dp1[N], dp2[N];
void preDFS(int v, int p = -1) {
St[v] = tim++;
for (int i = 1; i < 20; i++)
P[i][v] = P[i - 1][P[i - 1][v]];
for (int id : adj[v]) {
int u = from[id] ^ to[id] ^ v;
if (u != p) S[u] = S[v] + w[id], H[u] = H[v] + 1, P[0][u] = v, preDFS(u, v);
}
Ft[v] = tim;
}
int getpar(int v, int h) {
for (int i = h; i; i -= i & -i)
v = P[__builtin_ctz(i)][v];
return v;
}
int LCA(int v, int u) {
if (H[u] < H[v]) swap(u, v);
u = getpar(u, H[u] - H[v]);
for (int i = 19; ~i; i--)
if (P[i][v] != P[i][u])
u = P[i][u], v = P[i][v];
return u == v ? v : P[0][v];
}
void downDFS(int v) {
if (M[v]) dp1[v] = 0;
for (int u : adj[v]) {
downDFS(u);
if (dp1[u] < 1e18) dp1[v] = min(dp1[v], dp1[u] + S[u] - S[v]);
}
}
void upd(pair<pair<ll, ll>, pair<ll, ll>> &x, ll v, ll y) {
x.S = min(x.S, {y, v});
if (x.F > x.S) swap(x.S, x.F);
}
void upDFS(int v) {
if (M[v]) dp2[v] = 0;
pair<pair<ll, ll>, pair<ll, ll>> x = {{1e16, 1e16}, {1e16, 1e16}};
upd(x, v, dp2[v]);
for (int u : adj[v]) {
upd(x, u, dp1[u] + S[u] - S[v]);
}
for (int u : adj[v]) {
if (x.F.S == u) dp2[u] = x.S.F + S[u] - S[v];
else dp2[u] = x.F.F + S[u] - S[v];
dp2[u] = min(dp2[u], (ll) 1e18);
}
for (int u : adj[v]) upDFS(u);
}
void Init(int _n, int A[], int B[], int D[]) {
n = _n;
for (int i = 0; i + 1 < n; i++) {
from[i] = A[i], to[i] = B[i], w[i] = D[i];
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
preDFS(0);
for (int i = 0; i < n; i++) adj[i] = {};
for (int i = 0; i < n; i++) dp1[i] = dp2[i] = 1e18;
}
ll Query(int s, int X[], int t, int Y[]) {
vector<int> vec;
for (int i = 0; i < s; i++) vec.push_back(X[i]);
for (int i = 0; i < t; i++) vec.push_back(Y[i]), M[Y[i]] = 1;
sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
int k = SZ(vec);
for (int i = 0; i < k; i++) {
int p = LCA(vec[i], vec[(i + 1) % k]);
vec.push_back(p);
}
sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
vector<int> st = {vec[0]};
for (int i = 1; i < SZ(vec); i++) {
int v = vec[i];
while (St[st.back()] > St[v] || Ft[v] > Ft[st.back()])
st.pop_back();
assert(SZ(st));
adj[st.back()].push_back(v);
st.push_back(v);
}
downDFS(vec[0]);
upDFS(vec[0]);
ll ret = 1e18;
for (int i = 0; i < s; i++) ret = min(ret, min(dp1[X[i]], dp2[X[i]]));
for (int i = 0; i < SZ(vec); i++) dp1[vec[i]] = dp2[vec[i]] = 1e18, adj[vec[i]] = {};
for (int i = 0; i < t; i++) M[Y[i]] = 0;
return ret;
}
