#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
#define rall(x) x.rbegin(),x.rend()
using namespace std;
ll n;
vector<pair<ll,ll>> adj[500005];
vector<ll> sz(500005), dead(500005), parC(500005,-1), best(500005,1e15);
ll anc[500005][20], dista[500005][20], anc_size[500005];
ll dfs_size(ll x,ll p){
sz[x] = 1;
for(auto [y,w] : adj[x]){
if(y != p && !dead[y]){
sz[x] += dfs_size(y,x);
}
}
return sz[x];
}
ll dfs_centroid(ll x,ll p,ll compsize){
for(auto [y,w] : adj[x]){
if(y != p && !dead[y] && sz[y] > compsize/2) return dfs_centroid(y,x,compsize);
}
return x;
}
void dfs_dist(ll u,ll p,ll c,ll d){
anc[u][anc_size[u]] = c;
dista[u][anc_size[u]] = d;
anc_size[u]++;
for(auto [v,w] : adj[u]){
if(v!=p && !dead[v]) dfs_dist(v,u,c,d+w);
}
}
void build(ll x,ll p){
ll compsize = dfs_size(x,-1);
ll c = dfs_centroid(x,-1,compsize);
parC[c] = p;
dead[c] = 1;
dfs_dist(c,-1,c,0);
for(auto [y,w] : adj[c]){
if(!dead[y]) build(y,c);
}
}
void Init(int N,int A[],int B[],int D[]){
n = N;
for(int i=0;i<n;i++){
adj[i].clear();
dead[i] = 0;
parC[i] = -1;
best[i] = 1e15;
sz[i] = 0;
anc_size[i] = 0;
for(int j=0;j<20;j++) dista[i][j] = 0;
}
for(int i=0;i<n-1;i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
build(0,-1);
}
ll Query(int S,int A[],int T,int B[]){
vector<int> v;
for(int i=0;i<S;i++){
int u = A[i];
for(int j=0;j<anc_size[u];j++){
int c = anc[u][j];
ll d = dista[u][j];
if(best[c]==1e15) v.push_back(c);
best[c] = min(best[c],d);
}
}
ll ans = 1e18;
for(int i=0;i<T;i++){
int u = B[i];
for(int j=0;j<anc_size[u];j++){
int c = anc[u][j];
ll d = dista[u][j];
ans = min(ans,best[c]+d);
}
}
for(auto x : v) best[x] = 1e15;
return ans;
}
