#include<bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 5e5+5, mod = 1e9+7, L = 19;
const long long inf = 1e18;
int timer;
vector<ii> adj[N];
vector<ii> adj_[N];
long long d[N], d_[N];
int in[N], out[N];
long long mn1[N], mn2[N];
int typ[N];
int up[N][L];
void dfs(int u, int p) {
in[u] = ++timer;
d_[u] = d_[p]+1;
up[u][0] = p;
for (int i=1; i<L; i++) up[u][i] = up[up[u][i-1]][i-1];
for (auto [v, l]: adj[u]) {
if (v!=p) {
d[v] = d[u]+l;
dfs(v, u);
}
}
out[u] = timer;
}
int kth_ancestor(int u, int k) {
for (int i=0; i<L; i++) {
if(k>>i&1) u = up[u][i];
}
return u;
}
int lca(int u, int v) {
if (d_[u]!=d_[v]) {
if(d_[u]>d_[v]) swap(u, v);
v = kth_ancestor(v, d_[v]-d_[u]);
}
if(u==v) return u;
for (int i=L-1; i>=0; i--) {
if (up[u][i]!=up[v][i]) {
u = up[u][i]; v = up[v][i];
}
}
return up[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
timer = 0;
int rt;
for (int i=0; i<N-1; i++) {
A[i]++; B[i]++;
rt = A[i];
adj[A[i]].pb({B[i], D[i]});
adj[B[i]].pb({A[i], D[i]});
}
dfs(rt, 0);
}
bool cmp(ii a, ii b) {
if (in[a.fi] != in[b.fi]) return in[a.fi] < in[b.fi];
return a.se>b.se;
}
bool is_par(int u, int v) {
return (in[u]<=in[v] && out[v]<=out[u]);
}
long long ans;
void dfs_solve(int u, int p) {
if (typ[u]==1) mn1[u] = min(mn1[u], 0ll);
else if (typ[u]==2) mn2[u] = min(mn2[u], 0ll);
for (auto [v, l]: adj_[u]) {
if (v!=p) {
dfs_solve(v, u);
mn1[u] = min(mn1[u], l+mn1[v]);
mn2[u] = min(mn2[u], l+mn2[v]);
}
}
ans = min(ans, mn1[u]+mn2[u]);
}
long long Query(int S, int X[], int T, int Y[]) {
ans = inf;
vector<ii> v;
for (int i=0; i<S; i++) {
X[i]++;
v.pb({X[i], 1});
}
for (int i=0; i<T; i++) {
Y[i]++;
v.pb({Y[i], 2});
}
sort(all(v), cmp);
int tmp = sz(v);
for (int i=1; i<tmp; i++) {
v.pb({lca(v[i].fi, v[i-1].fi), 0});
}
sort(all(v), cmp);
v.erase(unique(all(v), [&](auto &a, auto &b){ return a.first == b.first; }), v.end());
for (int i=0; i<=sz(v); i++) {
adj_[i].clear();
mn1[i] = mn2[i] = inf;
typ[i] = 0;
}
int idx = 0;
stack<ii> st;
for (auto it: v) {
while (sz(st) && !is_par(st.top().fi, it.fi)) {
st.pop();
}
idx++;
typ[idx] = it.se;
if (sz(st)) {
adj_[st.top().se].pb({idx, d[it.fi]-d[st.top().fi]});
adj_[idx].pb({st.top().se, d[it.fi]-d[st.top().fi]});
}
st.push({it.fi, idx});
}
dfs_solve(1, 0);
return ans;
}
