#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const int MAXN = 5e5 + 5;
const ll inf = 1e18;
vector<pair<int, int>> g[MAXN];
int dead[MAXN], sz[MAXN];
bool is_a[MAXN], is_b[MAXN];
int n;
ll mn_dist;
int dfs_size(int u, int p) {
sz[u] = 1;
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
sz[u] += dfs_size(v, u);
}
return sz[u];
}
int dfs_centroid(int u, int p, int total_sz) {
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
if(sz[v] > total_sz / 2) return dfs_centroid(v, u, total_sz);
}
return u;
}
ll mn_a, mn_b;
void dfs_dist(int u, int p, ll d) {
if(is_a[u]) mn_a = min(mn_a, d);
if(is_b[u]) mn_b = min(mn_b, d);
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
dfs_dist(v, u, d + w);
}
}
void decompose(int u) {
int total_sz = dfs_size(u, 0);
int c = dfs_centroid(u, 0, total_sz);
dead[c] = 1;
ll best_a = (is_a[c] ? 0 : inf);
ll best_b = (is_b[c] ? 0 : inf);
mn_dist = min(mn_dist, best_a + best_b);
for(auto &[v, w] : g[c]) {
if(dead[v]) continue;
mn_a = inf;
mn_b = inf;
dfs_dist(v, c, (ll)w);
mn_dist = min(mn_dist, mn_a + best_b);
mn_dist = min(mn_dist, mn_b + best_a);
best_a = min(best_a, mn_a);
best_b = min(best_b, mn_b);
}
for(auto &[v, w] : g[c]) {
if(dead[v]) continue;
decompose(v);
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i, 1, n + 1) {
g[i].clear();
dead[i] = 0;
is_a[i] = false;
is_b[i] = false;
}
FOR(i, 0, n - 1) {
int u = A[i] + 1, v = B[i] + 1, w = D[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
}
ll Query(int S, int A[], int T, int B[]) {
fill(is_a, is_a + n + 1, 0);
fill(is_b, is_b + n + 1, 0);
fill(dead, dead + n + 1, 0);
FOR(i, 0, S) is_a[A[i] + 1] = 1;
FOR(i, 0, T) is_b[B[i] + 1] = 1;
mn_dist = inf;
decompose(1);
return mn_dist;
}
