#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#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=0){
this->sz = n;
t.assign(sz * 4 + 5, 0);
bn.assign(sz * 4 + 5, -1LL);
}
void push(int tl, int tr, int v){
if(bn[v] == -1LL) return;
if(tl != tr){
bn[v*2] = bn[v];
bn[v*2+1] = bn[v];
}
t[v] = (long long)(tr - tl + 1) * bn[v];
bn[v] = -1LL;
}
void update(int tl, int tr, int v, int l, int r, long long 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){
if(l>r) return;
update(1, sz, 1, l, r, (long long)x);
}
long long 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;
long long a = gt(tl, tm, v*2, l, r);
long long b = gt(tm+1, tr, v*2+1, l, r);
t[v] = t[v*2] + t[v*2+1];
return a + b;
}
long long get(int l, int r){
if(l>r) return 0LL;
return gt(1, sz, 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 = 0, sum = 0;
void dfs(int x, int pr){
p[x] = pr;
sz[x] = 1;
for(auto &ed : g[x]){
int to = (int)ed[0];
long long dist = ed[1];
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 &ed : g[x]){
int to = (int)ed[0];
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 &ed : g[x]){
int to = (int)ed[0];
if(to == pr || to == hv) continue;
head[to] = to;
hld(to, x);
}
}
int up(int x){
// if edge for node x (edge parent->x) is active then top is x
if(t.get((int)id[x], (int)id[x]) > 0) return x;
int h = (int)head[x];
// if entire chain head..x has no active edges, go above
if(t.get((int)id[h], (int)id[x]) == 0){
if(p[h] == h || p[h] == -1) return h;
else return up((int)p[h]);
}
// binary search by positions in HLD to find highest node in same component
int L = (int)id[h], R = (int)id[x];
while(L < R){
int M = (L + R) >> 1;
// check edges M..R: positions (M..R] correspond to edges (node at pos M+1 .. pos R)
// In our seg, we store edge state on position id[node] for node!=root.
long long ones = t.get(M, R);
if(ones == (long long)(R - M)) R = M;
else L = M + 1;
}
return (int)id_[L];
}
void root(int x){
int h = (int)head[x];
t.upd((int)id[h], (int)id[x], 1);
if(h == 0) return;
if(p[h] == -1) return;
root((int)p[h]);
}
void root2(int x){
int h = (int)head[x];
t.upd((int)id[h], (int)id[x], 0);
if(h == 0) return;
if(p[h] == -1) return;
root2((int)p[h]);
}
void Init(int N, int A[], int B[], int D[]){
// initialize globals and structures
n = N;
for(int i = 0; i < n; ++i){
g[i].clear();
id[i] = head[i] = id_[i] = p[i] = sz[i] = dep[i] = 0;
}
// read exactly N-1 edges from arrays A,B,D
for(int i = 0;i < n-1; ++i){
int a = A[i], b = B[i];
int d = D[i];
g[a].pb({b, d});
g[b].pb({a, d});
}
timer = 0;
// root at 0
p[0] = -1;
dep[0] = 0;
dfs(0, -1);
head[0] = 0;
hld(0, -1);
// initialize segtree size properly
t = Bit(n);
}
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;
vs.reserve(T);
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 < (int)vs.size(); ++i){
if(i == (int)vs.size() - 1 || vs[i+1][0] != vs[i][0]){
t.upd((int)id[(int)vs[i][0]], (int)id[(int)vs[i][0]], (int)vs[i][1]);
continue;
}
if(vs[i+1][1] > vs[i][1]) vs[i+1][1] = vs[i][1];
}
long long res = (long long)1e17 + 7;
for(int i = 0;i < S; ++i){
int u = up(X[i]);
if(t.get((int)id[u], (int)id[u]) == 0) continue;
res = min(res, (long long)(dep[X[i]] - dep[u]) + t.get((int)id[u], (int)id[u]));
}
for(auto &pr : vs){
int x = (int)pr[0];
t.upd((int)id[x], (int)id[x], 0);
}
return res;
}
