#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;
const int maxn = 500005;
int st[maxn * 4];
void upd(int p, int l, int r, int K, int V) {
if (p == 0) return;
if (l == r) {st[p] = V; return;}
int m = (l + r) >> 1;
if (K <= m) upd(p<<1, l, m, K, V);
else upd(p<<1|1, m+1, r, K, V);
st[p] = min(st[p<<1], st[p<<1|1]);
}
int qry(int p, int l, int r, int L, int R) {
if (R < l || r < L) return INF;
if (L <= l && r <= R) return st[p];
int m = (l + r) >> 1;
return min(qry(p<<1, l, m, L, R), qry(p<<1|1, m+1, r, L, R));
}
int st2[maxn * 4];
void upd2(int p, int l, int r, int K, int V) {
if (l == r) {st2[p] = V; return;}
int m = (l + r) >> 1;
if (K <= m) upd2(p<<1, l, m, K, V);
else upd2(p<<1|1, m+1, r, K, V);
st2[p] = min(st2[p<<1], st2[p<<1|1]);
}
int qry2(int p, int l, int r, int L, int R) {
if (R < l || r < L) return INF;
if (L <= l && r <= R) return st2[p];
int m = (l + r) >> 1;
return min(qry2(p<<1, l, m, L, R), qry2(p<<1|1, m+1, r, L, R));
}
Tree<maxn> tree;
LCA<maxn, 20> lca;
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]});
}
fill(st, st+maxn*4, INF);
fill(st2, st2+maxn*4, INF);
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]);
upd(1, 0, tree.cnt-1, tree.st[X[i]], dist[X[i]]);
}
for (int i = 0; i < T; i++) {
nds.push_back(Y[i]);
upd2(1, 0, tree.cnt-1, 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 i = 0... tree.cnt-1 print queries @ [i, i] for st & st2
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) {
// output queries
ans = min(ans, -2*dist[i] + qry(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1) + qry2(1, 0, tree.cnt-1, tree.st[i], tree.en[i]-1));
}
for (int i = 0; i < S; i++) upd(1, 0, tree.cnt-1, tree.st[X[i]], INF);
for (int i = 0; i < T; i++) upd2(1, 0, tree.cnt-1, tree.st[Y[i]], INF);
return ans;
}
