#include<bits/stdc++.h>
using namespace std;
const int M = 5e5 + 1, K = 20;
const long long INF = 4e18;
int p[M];
char d[M];
long long dist[K][M], ans[M];
bool used[M];
vector < pair < int, int > > g[M];
int dfs(int v, int size, int ¢er, int pr = -1){
int sz = 1;
for(auto it : g[v]){
int to = it.first;
if(to != pr && !used[to]){
sz += dfs(to, size, center, v);
}
}
if(center == -1 && sz >= size / 2){
center = v;
}
return sz;
}
void dfs1(int v, int depth, int pr = 0, long long len = 0){
dist[depth][v] = len;
for(auto it : g[v]){
int to = it.first, val = it.second;
if(to != pr && !used[to]){
dfs1(to, depth, v, len + val);
}
}
}
void build(int v, int pr = -1, int depth = 0){
int center = -1, tmp = 0;
dfs(v, dfs(v, 0, tmp), center);
dfs1(center, depth);
used[center] = true;
d[center] = depth;
p[center] = pr;
for(auto it : g[center]){
int to = it.first;
if(!used[to]){
build(to, center, depth + 1);
}
}
}
void Init(int N, int A[], int B[], int D[]){
for(int i = 0; i < N - 1; i++){
g[A[i]].push_back(make_pair(B[i], D[i]));
g[B[i]].push_back(make_pair(A[i], D[i]));
}
for(int i = 0; i < N; i++){
ans[i] = INF;
}
build(0);
}
long long Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i++){
int cur = X[i];
while(cur != -1){
ans[cur] = min(ans[cur], dist[d[cur]][X[i]]);
cur = p[cur];
}
}
long long mn = INF;
for(int i = 0; i < T; i++){
int cur = Y[i];
while(cur != -1){
mn = min(mn, dist[Y[i]][d[cur]] + ans[cur]);
cur = p[cur];
}
}
for(int i = 0; i < S; i++){
int cur = X[i];
while(cur > 0){
ans[cur] = INF;
cur = p[cur];
}
}
return mn;
}
