#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int n;
const int N = 2e6 + 5;
vector < pii > g[N];
int * SZ;
void dfs_sz(int v = 0) {
SZ[v] = 1;
for (auto & u : g[v]) {
if (SZ[u.fi] != -1)
continue;
dfs_sz(u.fi);
SZ[v] += SZ[u.fi];
if (SZ[u.fi] >= SZ[g[v][0].fi])
swap(u, g[v][0]);
}
}
int * in;
int * out;
int * rin;
int * nxt;
int * pr;
int Time = 0;
ll * D;
void dfs_hld(int v = 0) {
in[v] = ++Time;
rin[in[v]] = v;
for (auto u : g[v]) {
if (D[u.fi] != -1)
continue;
nxt[u.fi] = (u == g[v][0] ? nxt[v] : u.fi);
D[u.fi] = u.se + D[v];
pr[u.fi] = v;
dfs_hld(u.fi);
}
out[v] = Time;
}
void Init(int NN, int A[], int B[], int DD[]) {
n = NN;
D = new ll[n + 5];
pr = new int[n + 5];
SZ = new int[n + 5];
in = new int[n + 5];
out = new int[n + 5];
nxt = new int[n + 5];
rin = new int[n + 5];
for (int i = 0;i < n;++i) {
g[A[i]].pb(mp(B[i],DD[i]));
g[B[i]].pb(mp(A[i],DD[i]));
}
for (int i = 0;i < n;++i)
SZ[i] = D[i] = -1;
D[0] = 0;
dfs_sz();
dfs_hld();
pr[0] = -1;
}
vector < pair < ll , int > > add[N],del[N];
long long Query(int SS, int X[], int T, int Y[]) {
vi a,b;
for (int i = 0;i < SS;++i)
a.pb(X[i]);
for (int i = 0;i < T;++i)
b.pb(Y[i]);
sort(all(a),[&](int x,int y) {
return D[x] < D[y];
});
sort(all(b),[&](int x,int y) {
return D[x] < D[y];
});
set < int > s1;
for (auto it : a) {
int node = it;
while (node >= 0 && !s1.count(in[node])) {
s1.insert(in[nxt[node]]);
s1.insert(in[node]);
add[in[nxt[node]]].pb(mp(D[it],0));
del[in[node]].pb(mp(D[it],0));
node = pr[nxt[node]];
}
}
set < int > s2;
for (auto it : b) {
int node = it;
while (node >= 0 && !s2.count(in[node])) {
s2.insert(in[nxt[node]]);
s2.insert(in[node]);
add[in[nxt[node]]].pb(mp(D[it],1));
del[in[node]].pb(mp(D[it],1));
node = pr[nxt[node]];
}
}
set < int > ss = s1;
for (auto it : s2)
ss.insert(it);
ll ans = 1e18;
multiset < ll > S[2];
ll mn[2] = {ans,ans};
for (auto i : ss) {
for (auto it : add[i]) {
S[it.se].insert(it.fi);
smin(mn[it.se],it.fi);
}
smin(ans,mn[0] + mn[1] - 2 * D[rin[i]]);
for (auto it : del[i]) {
S[it.se].erase(S[it.se].find(it.fi));
if (mn[it.se] == it.fi) {
if (S[it.se].empty()) {
mn[it.se] = 1e18;
} else {
mn[it.se] = *S[it.se].begin();
}
}
}
add[i].clear();
del[i].clear();
}
return ans;
}
