#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int maxN = 5e5 + 7;
int n, level[maxN], par[20][maxN], st[maxN], ed[maxN], cnt = 0, sz = 0;
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN];
vector < pair <int, int> > edge[maxN];
void dfs(int u, int p){
st[u] = ++cnt;
for(pair <int, int> to : edge[u]){
int v = to.fi, w = to.se;
if(v == p) continue;
par[0][v] = u;
level[v] = level[u] + 1;
depth[v] = depth[u] + w;
dfs(v, u);
}
ed[u] = cnt;
}
int lca(int u, int v){
if(level[u] > level[v]) swap(u, v);
for(int i = 19; i >= 0; i--) if(level[par[i][v]] >= level[u]) v = par[i][v];
for(int i = 19; i >= 0; i--) if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
if(u == v) return u;
return par[0][u];
}
bool cmp(pair <int, int> x, pair <int, int> y){
return st[x.fi] < st[y.fi];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++){
A[i]++, B[i]++;
edge[A[i]].pb(mp(B[i], D[i]));
edge[B[i]].pb(mp(A[i], D[i]));
}
par[0][1] = 1;
level[1] = 1;
dfs(1, 1);
for(int i = 1; i < 20; i++){
for(int j = 1; j <= n; j++){
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
st[n + 1] = 1e9;
}
pair <long long, long long> solve(){
int u = cur[cnt].fi;
long long A = 1e18, B = 1e18;
if(cur[cnt].se == 0) A = min(A, depth[u]);
if(cur[cnt].se == 1) B = min(B, depth[u]);
cnt++;
if(cnt > sz) return mp(A, B);
while(cur[cnt].fi == u){
if(cur[cnt].se == 0) A = min(A, depth[u]);
if(cur[cnt].se == 1) B = min(B, depth[u]);
cnt++;
}
while(ed[u] >= st[cur[cnt].fi]){
pair <long long, long long> tmp = solve();
A = min(A, tmp.fi), B = min(B, tmp.se);
}
ans = min(ans, A + B - 2LL * depth[u]);
return mp(A, B);
}
long long Query(int S, int X[], int T, int Y[]) {
ans = 1e18;
sz = 0;
for(int i = 0; i < S; i++) cur[++sz] = mp(X[i] + 1, 0);
for(int i = 0; i < T; i++) cur[++sz] = mp(Y[i] + 1, 1);
sort(cur + 1, cur + 1 + sz, cmp);
int sv = sz;
for(int i = 1; i < sv; i++) cur[++sz] = mp(lca(cur[i].fi, cur[i + 1].fi), 2);
cur[++sz] = mp(n + 1, 0);
sort(cur + 1, cur + 1 + sz, cmp);
//for(int i = 1; i <= sz; i++) cout << cur[i].fi << endl;
cnt = 1;
solve();
return ans;
}
