#include <bits/stdc++.h>
#include"factories.h"
using namespace std;
#define ll long long
const int N = 500005;
vector< array<int, 2 > > adj[N];
int paiC[N];
bool blocked[N];
int sz[N];
ll vl[N];
ll maxint = 1000000000000000000ll;
int n;
ll dist[N][20];
int layer[N];
void computa(int x , int y){
sz[x] = 1;
for(auto w : adj[x]){
if(blocked[w[0]] || y == w[0]) continue;
computa(w[0] , x);
sz[x] += sz[w[0]];
}
}
int find_C(int x , int y , int root){
int centroid = x;
for(auto w : adj[x]){
if(blocked[w[0]] || y == w[0]) continue;
if(sz[w[0]] > sz[root]/2) centroid = find_C(w[0] , x , root);
}
return centroid;
}
void fill_dp(int x , int y , int pai , int root , ll dis){
dist[x][layer[root]] = dis;
for(auto w : adj[x]){
if(blocked[w[0]] || y == w[0]) continue;
fill_dp(w[0] , x , pai, root ,(ll)dis + 1ll*w[1]);
}
}
void decompose(int x = 0, int pai = -1){
computa(x , x);
x = find_C(x , x , x);
paiC[x] = pai;
if(pai == -1) layer[x] = 0;
else layer[x] = layer[pai] + 1;
fill_dp(x , x , pai , x,0);
blocked[x] = true;
for(auto w : adj[x]){
if(!blocked[w[0]])
decompose(w[0] , x);
}
}
void Init(int N, int A[], int B[], int D[]){
for(int i = 0 ; i < N - 1 ; i ++){
adj[A[i]].push_back({B[i] , D[i]});
adj[B[i]].push_back({A[i] , D[i]});
}
n = N;
decompose();
for(int i = 0 ; i < N ; i ++){
vl[i] = maxint;
}
}
long long Query(int S, int X[], int T, int Y[]){
for(int i = 0 ; i < S ; i ++){
ll currdis = 0;
int x = X[i];
while(x != -1){
vl[x] = min(vl[x] , dist[X[i]][layer[x]]);
x = paiC[x];
}
}
ll ans = maxint;
for(int i = 0 ; i < T ; i ++){
ll currdis = 0;
int x = Y[i];
while(x != -1){
ans = min(ans , dist[Y[i]][layer[x]] + vl[x]);
x = paiC[x];
}
}
for(int i = 0 ; i < S ; i ++){
int x = X[i];
while(x != -1){
vl[x] = maxint;
x = paiC[x];
}
}
return ans;
}
