#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define ll long long
#define fi first
#define se second
const ll N = 5e5 + 5, M = 1e9 + 7, LG = 20;
ll n , A[N] , sz[N] , P[N] , u , v , sp[N][LG] , Dep[N] , m , H[N] , B[N] ;
int Ne , Q , L[N] , R[N] , D[N] , S , T , X[N] , Y[N];
vector<pair<ll,ll>> lis[N] ;
vector<ll> used , Dis[N];
bool dead[N];
void dfs(ll v , ll par , ll wi){
Dep[v] = Dep[par] + wi;
H[v] = H[par] + 1;
sp[v][0] = par;
for (auto u : lis[v]){
if (u.fi == par) continue;
dfs(u.fi , v , u.se);
}
}
void pre_dfs(ll v , ll par){
sz[v] = 1;
for (auto u : lis[v]){
if (u.fi == par || dead[u.fi]) continue;
pre_dfs(u.fi , v);
sz[v] += sz[u.fi];
}
}
ll ce(ll v , ll par , ll root){
for (auto u : lis[v]){
if (u.fi != par && !dead[u.fi] && 2 * sz[u.fi] > sz[root]) return ce(u.fi , v , root);
}
return v;
}
void dist(ll v , ll par , ll di){
for (auto u : lis[v]){
if (u.fi != par && !dead[u.fi]){
dist(u.fi , v , di + u.se);
}
}
Dis[v].pb(di);
}
void get(ll v , ll par){
pre_dfs(v , par);
ll c = ce(v , par , v);
P[c] = par;
dead[c] = 1;
dist(c , par , 0);
for (auto u : lis[c]){
if (!dead[u.fi]) get(u.fi , c);
}
}
void upd(ll v , ll par , int h){
while(par != -1){
used.pb(par);
A[par] = min(A[par] , Dis[v][h]);
par = P[par];
h++;
}
}
void upd1(ll v , ll par , int h){
while(par != -1){
used.pb(par);
B[par] = min(B[par] , Dis[v][h]);
par = P[par];
h++;
}
}
ll cal(int v , int par){
ll ans = 1e18;
while(par != -1){
ans = min(ans , A[par] + B[par]);
par = P[par];
}
return ans;
}
void Init(int N, int L[], int R[], int D[]) {
n = N;
for (int i=1 ; i<=N ; i++){
lis[i].clear();
}
for (ll i=0 ; i<n-1 ; i++){
u = L[i]+1;
v = R[i]+1;
m = D[i];
lis[u].pb({v,m});
lis[v].pb({u,m});
}
for (ll i=0 ; i<=N ; i++) A[i] = B[i] = 1e18;
dfs(1 , 0 , 0);
for (ll j=1 ; j<LG ; j++){
for (ll i=1 ; i<=n ; i++){
sp[i][j] = sp[sp[i][j-1]][j-1];
}
}
get(1 , -1);
for (int i=1 ; i<=n ; i++){
reverse(Dis[i].begin() , Dis[i].end());
}
}
long long Query(int S, int X[], int T, int Y[]) {
for (ll i=0 ; i<S ; i++){
upd(X[i]+1 ,X[i]+1,0);
}
for (ll i=0 ; i<T ; i++){
upd1(Y[i]+1 ,Y[i]+1,0);
}
ll bs = 1e18;
for (ll i=0 ; i<T ; i++){
bs = min(bs , cal(Y[i]+1 ,Y[i]+1));
}
for (int i : used){
A[i] = B[i] = 1e18;
}
used.clear();
return bs;
}
