#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 = 1e6 + 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<int> used;
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 get(ll v , ll par){
pre_dfs(v , par);
ll c = ce(v , par , v);
P[c] = par;
dead[c] = 1;
for (auto u : lis[c]){
if (!dead[u.fi]) get(u.fi , c);
}
}
ll dist(ll u , ll v){
if (H[v] > H[u]){
swap(u , v);
}
ll dif = H[u] - H[v] , u1 = u , v1 = v;
for (ll i=LG-1 ; i>=0 ; i--){
if ((1<<i) & dif){
u = sp[u][i];
}
}
if (u == v){
return Dep[u1] - Dep[v1];
}
for (ll i=LG-1 ; i>=0 ; i--){
if (sp[u][i] != sp[v][i]){
u = sp[u][i];
v = sp[v][i];
}
}
return Dep[u1] + Dep[v1] - 2 * Dep[sp[u][0]];
}
void upd(ll v , ll par){
while(par != -1){
used.pb(par);
A[par] = min(A[par] , dist(v , par));
par = P[par];
}
}
void upd1(ll v , ll par){
while(par != -1){
used.pb(par);
B[par] = min(B[par] , dist(v , par));
par = P[par];
}
}
ll cal(ll v , ll 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);
}
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);
}
for (ll i=0 ; i<T ; i++){
upd1(Y[i]+1 ,Y[i]+1);
}
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;
}
