#include "factories.h"
#define pb push_back
#define ar array
const int NN = 5e5 + 5;
int n,m,k;
struct Bit {
int sz;
vector<long long> t, bn;
Bit (int n){
this->sz = n;
t.resize(sz * 4);
bn.resize(sz * 4);
for(int i = 0;i<sz*4;i++)bn[i] = -1;
}
void push(int tl, int tr, int v){
if(bn[v] == -1)return;
if(tl != tr){
bn[v*2] = bn[v];
bn[v*2+1] = bn[v];
}
t[v] = (tr - tl + 1) * bn[v];
bn[v] = -1;
}
void update(int tl, int tr, int v, int l, int r, int val){
push(tl, tr, v);
if(r < l || tr < l || r < tl)return;
if(l <= tl && tr <= r){
bn[v] = val;
push(tl, tr, v);
return;
}
int tm = (tl + tr) / 2;
update(tl, tm, v*2, l, r, val); update(tm+1, tr, v*2+1, l, r, val);
t[v] = t[v*2] + t[v*2+1];
}
void upd(int l, int r, int x){
update(1, n, 1, l, r, x);
}
int gt(int tl, int tr, int v, int l, int r){
push(tl, tr, v);
if(r < l || tr < l || r < tl)return 0ll;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr) / 2;
int a = gt(tl, tm, v*2, l, r);
int b = gt(tm+1, tr, v*2+1, l, r);
t[v] = t[v*2] + t[v*2+1];
return a + b;
}
int get(int l, int r){
return gt(1, n, 1, l, r);
}
};
Bit t(NN);
vector<ar<long long,2>>g[NN];
vector<long long>id(NN), head(NN), id_(NN), p(NN), sz(NN), dep(NN);
int timer, sum;
void dfs(int x, int pr){
p[x] = pr;
sz[x] = 1;
for(auto [to, dist] : g[x]){
if(to == pr)continue;
dep[to] = dep[x] + dist;
dfs(to, x);
sz[x] += sz[to];
}
}
void hld(int x, int pr){
int hv = -1;
timer += 1; id[x] = timer; id_[timer] = x;
for(auto [to, dist] : g[x]){
if(to == pr)continue;
if(hv == -1 || sz[hv] < sz[to])hv = to;
}
if(hv != -1){
head[hv] = head[x];
hld(hv, x);
}
for(auto [to, dist] : g[x]){
if(to == pr || to == hv)continue;
head[to] = to;
hld(to, x);
}
}
int up(int x){
if(t.get(id[x], id[x]) > 0)return x;
int h = head[x];
if(t.get(id[h], id[x]) == 0){
if(p[h] == h)return h;
else return up(p[h]);
}
for(int i = 19;i>=0;i--){
int num = id[x] - (1ll << i);
if(num < id[h])continue;
int node = id_[num];
if(t.get(num, id[x]) == 0){
x = node;
}
}
return p[x];
}
void root(int x){
int h = head[x];
t.upd(id[h], id[x], 1);
if(h == 0)return;
root(p[h]);
}
void root2(int x){
int h = head[x];
t.upd(id[h], id[x], 0);
if(h == 0)return;
root2(p[h]);
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0;i<n;i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
dfs(0, 0);
head[0] = 0;
hld(0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0;i<S;i++){
root(X[i]);
}
vector<ar<long long,2>>vs;
for(int i = 0;i<T;i++){
int u = up(Y[i]);
vs.pb({u, dep[Y[i]] - dep[u]});
}
for(int i = 0;i<S;i++){
root2(X[i]);
}
sort(vs.begin(), vs.end());
for(int i = 0;i<vs.size();i++){
if(i == vs.size() - 1 || vs[i+1][0] != vs[i][0]){
t.upd(id[vs[i][0]], id[vs[i][0]], vs[i][1]);
continue;
}
vs[i+1][1] = min(vs[i+1][1], vs[i][1]);
}
long long res = 1e17 + 7;
for(int i = 0;i<S;i++){
int u = up(X[i]);
if(t.get(id[u], id[u]) == 0)continue;
// cout << u << " " << X[i] << " " << t.get(id[u], id[u]) << " ";
res = min(res, dep[X[i]] - dep[u] + t.get(id[u], id[u]));
}
for(auto [x, u] : vs){
t.upd(id[x], id[x], 0);
}
return res;
}
