#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1000000000000000000LL;
const int MAXN = 500000;
vector <pair <int, int>> graf[MAXN+5];
pair <int, ll> parents[MAXN+5][20];
int dokle[MAXN+5];
bool erased[MAXN+5];
int sz[MAXN+5];
ll mnd[MAXN+5];
void dfs_size(int v, int p){
sz[v] = 1;
for(auto c : graf[v]){
if(erased[c.first] || c.first == p) continue;
dfs_size(c.first, v);
sz[v] += sz[c.first];
}
}
int find_centroid(int v, int p, int svi){
for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > svi) return find_centroid(c.first, v, svi);
return v;
}
void dfs_depth(int v, int p, ll dst, int root){
parents[v][++dokle[v]] = {root, dst};
for(auto c : graf[v]) if(!erased[c.first] && c.first != p) dfs_depth(c.first, v, dst + c.second, root);
}
void decompose(){
queue <int> q;
q.push(1);
while(!q.empty()){
int v = q.front();
q.pop();
dfs_size(v, 0);
v = find_centroid(v, 0, sz[v]);
dfs_depth(v, 0, 0, v);
erased[v] = 1;
for(auto c : graf[v]) if(!erased[c.first]) q.push(c.first);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0; i<N-1; i++){
A[i]++;
B[i]++;
graf[A[i]].push_back({B[i], D[i]});
graf[B[i]].push_back({A[i], D[i]});
}
decompose();
for(int i=1; i<=N; i++) reverse(parents[i]+1, parents[i]+1+dokle[i]);
for(int i=1; i<=N; i++) mnd[i] = INF;
}
void upd(int x){
for(int i=1; i<=dokle[x]; i++) if(mnd[parents[x][i].first] > parents[x][i].second) mnd[parents[x][i].first] = parents[x][i].second;
}
void brisi(int x){
for(int i=1; i<=dokle[x]; i++){
pair <int, ll> c = parents[x][i];
if(mnd[c.first] == INF) return;
mnd[c.first] = INF;
}
}
ll query(int x){
ll res = INF;
for(int i=1; i<=dokle[x]; i++) res = min(res, parents[x][i].second + mnd[parents[x][i].first]);
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
ll mn = INF;
if(S < T){
for(int i=0; i<S; i++) upd(X[i]+1);
for(int i=0; i<T; i++) mn = min(mn, query(Y[i]+1));
for(int i=0; i<S; i++) brisi(X[i]+1);
}
else{
for(int i=0; i<T; i++) upd(Y[i]+1);
for(int i=0; i<S; i++) mn = min(mn, query(X[i]+1));
for(int i=0; i<T; i++) brisi(Y[i]+1);
}
return mn;
}
