#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Seg {
int n;
vector<ll> tree, lazy;
Seg(): n(0) {}
Seg(int n_){ init(n_); }
void init(int n_){
n = n_;
tree.assign(4*n+5, 0);
lazy.assign(4*n+5, LLONG_MAX);
}
inline void apply(int v, int l, int r, ll val){
tree[v] = val * (r - l + 1);
lazy[v] = val;
}
inline void push(int v, int l, int r){
if(lazy[v]==LLONG_MAX) return;
if(l!=r){
int m=(l+r)>>1;
apply(v<<1, l, m, lazy[v]);
apply(v<<1|1, m+1, r, lazy[v]);
}
lazy[v]=LLONG_MAX;
}
void upd(int v,int l,int r,int ql,int qr,ll val){
if(ql>qr || r<ql || qr<l) return;
if(ql<=l && r<=qr){ apply(v,l,r,val); return; }
push(v,l,r);
int m=(l+r)>>1;
upd(v<<1,l,m,ql,qr,val);
upd(v<<1|1,m+1,r,ql,qr,val);
tree[v]=tree[v<<1]+tree[v<<1|1];
}
ll get(int v,int l,int r,int ql,int qr){
if(ql>qr || r<ql || qr<l) return 0;
if(ql<=l && r<=qr) return tree[v];
push(v,l,r);
int m=(l+r)>>1;
return get(v<<1,l,m,ql,qr)+get(v<<1|1,m+1,r,ql,qr);
}
void range_assign(int l,int r,int val){ if(l>r) return; upd(1,1,n,l,r,(ll)val); }
ll range_sum(int l,int r){ if(l>r) return 0; return get(1,1,n,l,r); }
};
static int Nglob = 0;
static vector<vector<pair<int,int>>> g;
static vector<int> parent_v, sz_v, idv, id_rev, head;
static vector<ll> dep;
static int timer_;
static Seg seg;
void dfs(int u,int p){
parent_v[u]=p;
sz_v[u]=1;
for(auto &e: g[u]){
int v=e.first, w=e.second;
if(v==p) continue;
dep[v]=dep[u]+(ll)w;
dfs(v,u);
sz_v[u]+=sz_v[v];
}
}
void hld(int u,int p){
int heavy=-1;
for(auto &e: g[u]){
int v=e.first;
if(v==p) continue;
if(heavy==-1 || sz_v[v]>sz_v[heavy]) heavy=v;
}
timer_++;
idv[u]=timer_;
id_rev[timer_]=u;
if(heavy!=-1){
head[heavy]=head[u];
hld(heavy,u);
}
for(auto &e: g[u]){
int v=e.first;
if(v==p || v==heavy) continue;
head[v]=v;
hld(v,u);
}
}
int up_node(int x){
while(true){
int h=head[x];
int hid=idv[h], xid=idv[x];
if(hid+1 <= xid){
ll ones = seg.range_sum(hid+1, xid);
ll need = (ll)(xid - hid);
if(ones == need){
if(parent_v[h]==-1) return h;
x = parent_v[h];
continue;
} else {
int L = hid+1, R = xid;
while(L < R){
int M = (L + R) >> 1;
ll s = seg.range_sum(M, xid);
ll need2 = (ll)(xid - M + 1);
if(s == need2) R = M;
else L = M + 1;
}
int topnode = id_rev[L-1];
return topnode;
}
} else {
if(parent_v[h]==-1) return h;
x = parent_v[h];
continue;
}
}
}
void set_path_up(int x,int val){
while(true){
int h=head[x];
int hid=idv[h], xid=idv[x];
if(hid+1 <= xid) seg.range_assign(hid+1, xid, val);
if(parent_v[h]==-1) break;
x = parent_v[h];
}
}
void Init(int N, int A[], int B[], int D[]){
Nglob = N;
g.assign(Nglob, {});
parent_v.assign(Nglob, -1);
sz_v.assign(Nglob, 0);
idv.assign(Nglob, 0);
id_rev.assign(Nglob+1, 0);
head.assign(Nglob, 0);
dep.assign(Nglob, 0);
timer_ = 0;
for(int i=0;i<Nglob-1;i++){
int a=A[i], b=B[i], d=D[i];
g[a].push_back({b,d});
g[b].push_back({a,d});
}
dep[0]=0;
dfs(0,-1);
head[0]=0;
hld(0,-1);
seg.init(Nglob);
}
long long Query(int S, int X[], int T, int Y[]){
for(int i=0;i<S;i++) set_path_up(X[i], 1);
vector<pair<int,ll>> vs; vs.reserve(T);
for(int i=0;i<T;i++){
int y=Y[i];
int u = up_node(y);
ll dist = dep[y] - dep[u];
vs.emplace_back(u, dist);
}
for(int i=0;i<S;i++) set_path_up(X[i], 0);
unordered_map<int,ll> best;
best.reserve(vs.size()*2+3);
for(auto &pr: vs){
int u=pr.first; ll d=pr.second;
auto it = best.find(u);
if(it==best.end()) best[u]=d;
else if(d < it->second) it->second = d;
}
for(auto &kv: best){
int u = kv.first;
ll val = kv.second;
seg.range_assign(idv[u], idv[u], (int)val);
}
ll ans = LLONG_MAX;
for(int i=0;i<S;i++){
int x = X[i];
int u = up_node(x);
ll cell = seg.range_sum(idv[u], idv[u]);
if(cell==0) continue;
ll cand = (dep[x] - dep[u]) + cell;
if(cand < ans) ans = cand;
}
for(auto &kv: best){
seg.range_assign(idv[kv.first], idv[kv.first], 0);
}
if(ans==LLONG_MAX) return -1;
return ans;
}
