#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll n;
vector<pair<ll,ll>> adj[500005];
vector<ll> sz(500005), dead(500005), parC(500005,-1), best(500005,1e15);
ll dista[500005][20];
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 d,ll depth){
dista[u][depth] = d;
for(auto [v,w] : adj[u]){
if(v!=p && !dead[v]) dfs_dist(v,u,d+w,depth+1);
}
}
void build(ll x,ll p,ll depth=0){
ll compsize = dfs_size(x,-1);
ll c = dfs_centroid(x,-1,compsize);
parC[c] = p;
dead[c] = 1;
dfs_dist(c,-1,0,depth);
for(auto [y,w] : adj[c]){
if(!dead[y]) build(y,c,depth+1);
}
}
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;
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,0);
}
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 depth=0; depth<20; depth++){
if(dista[u][depth]==0 && depth!=0) break;
if(best[u]==1e15) v.push_back(u);
best[u] = min(best[u], dista[u][depth]);
}
}
ll ans = 1e18;
for(int i=0;i<T;i++){
int u = B[i];
for(int depth=0; depth<20; depth++){
if(dista[u][depth]==0 && depth!=0) break;
ans = min(ans, best[u]+dista[u][depth]);
}
}
for(auto x : v) best[x] = 1e15;
return ans;
}
