#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<int SZ> struct Tree {
vector<pair<int,int>> adj[SZ];
int st[SZ], en[SZ], cnt=0;
void flatten(int nd, int par) {
st[nd] = cnt++;
for (auto i : adj[nd])
if (i.first != par)
flatten(i.first, nd);
en[nd] = cnt;
}
};
template<int SZ, int LOG> struct LCA {
int bl[SZ][LOG];
int dpth[SZ], st[SZ], en[SZ], cnt=0;
Tree<SZ>* tree;
void init_dfs(int nd, int par) {
dpth[nd] = dpth[par]+1;
bl[nd][0] = par;
for (int i = 1; i < LOG; i++)
bl[nd][i] = bl[bl[nd][i-1]][i-1];
for (auto& i : tree->adj[nd])
if (i.first != par)
init_dfs(i.first, nd);
}
void init(Tree<SZ>* TREE, int R = 0) {
tree = TREE;
init_dfs(R, R);
}
int operator()(int a, int b) {
if (dpth[a] > dpth[b]) swap(a, b);
for (int i = 19; i >= 0; i--)
if (!(tree->st[bl[b][i]] <= tree->st[a] && tree->en[a] <= tree->en[bl[b][i]]))
b = bl[b][i];
return bl[b][0];
}
};
const int INF = LLONG_MAX >> 1ll;
#define T int
#define OPERATION(a, b) min(a,b)
struct ND {
static T ident;
ND* ch[2] = { nullptr, nullptr };
T v, f;
ND() { ch[0] = ch[1] = nullptr; }
ND(T V, T F, ND* l, ND* r) {
v = V, f = F;
ch[0] = l, ch[1] = r;
}
inline void create() {
if (!ch[0]) {ch[0] = new ND(v, f, nullptr, nullptr);}
if (!ch[1]) {ch[1] = new ND(v, f, nullptr, nullptr);}
}
inline void push(int l, int r) {
v = OPERATION(v, f);
f = ND::ident;
if (l != r) create();
}
void upd(int l, int r, int L, int R, T K) {
push(l, r);
if (R < l || r < L) return;
if (L <= l && r <= R) {
v = K, f = K;
return;
}
int m = (l + r) >> 1;
ch[0]->upd(l, m, L, R, K);
ch[1]->upd(m+1, r, L, R, K);
v = OPERATION(ch[0]->v, ch[1]->v);
}
T qry(int l, int r, int L, int R) {
push(l, r);
if (R < l || r < L) return ND::ident;
if (L <= l && r <= R) return v;
int m = (l + r) >> 1;
return OPERATION(ch[0]->qry(l,m,L,R), ch[1]->qry(m+1,r,L,R));
}
~ND() { delete ch[0]; delete ch[1]; ch[0] = ch[1] = nullptr; }
};
T ND::ident = INF;
#undef T
#undef OPERATION
const int maxn = 500005;
Tree<maxn> tree;
LCA<maxn, 20> lca;
ND root1 = ND(INF, INF, nullptr, nullptr),
root2 = ND(INF, INF, nullptr, nullptr);
int dist[maxn];
void dfs(int nd, int par) {
for (auto i : tree.adj[nd])
if (i.first != par) {
dist[i.first] = dist[nd] + i.second;
dfs(i.first, nd);
}
}
void Init(signed N, signed A[], signed B[], signed D[]) {
for (int i = 0; i < N-1; i++) {
tree.adj[A[i]].push_back({B[i], D[i]});
tree.adj[B[i]].push_back({A[i], D[i]});
}
tree.flatten(0, 0);
lca.init(&tree, 0);
dist[0] = 0;
dfs(0, 0);
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
vector<int> nds;
for (int i = 0; i < S; i++) {
nds.push_back(X[i]);
root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], dist[X[i]]);
}
for (int i = 0; i < T; i++) {
nds.push_back(Y[i]);
root2.upd(0, tree.cnt-1, tree.st[Y[i]], tree.st[Y[i]], dist[Y[i]]);
}
sort(nds.begin(), nds.end(), [](int a, int b) { return tree.st[a] < tree.st[b]; });
vector<int> v;
for (int i = 0; i < nds.size()-1; i++) v.push_back(lca(nds[i], nds[i+1]));
for (auto i : v) nds.push_back(i);
sort(nds.begin(), nds.end(), [](int a, int b) { return tree.st[a] < tree.st[b]; });
int ans = INF;
for (auto i : nds) {
ans = min(ans, -2*dist[i] + root1.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1) + root2.qry(0, tree.cnt-1, tree.st[i], tree.en[i]-1));
}
for (int i = 0; i < S; i++) root1.upd(0, tree.cnt-1, tree.st[X[i]], tree.st[X[i]], INF);
for (int i = 0; i < T; i++) root2.upd(0, tree.cnt-1, tree.st[Y[i]], tree.st[Y[i]], INF);
return ans;
}
