#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ar array
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 x){
tree[v] = x * (r - l + 1);
lazy[v] = x;
}
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 x){
if(ql > qr || r < ql || qr < l) return;
if(ql <= l && r <= qr){
apply(v, l, r, x);
return;
}
push(v, l, r);
int m = (l + r) >> 1;
upd(v<<1, l, m, ql, qr, x);
upd(v<<1|1, m+1, r, ql, qr, x);
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);
}
// helpers
void range_assign(int l, int r, ll x){
if(l>r) return;
upd(1,1,n,l,r,x);
}
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> id_, id_rev, head, parent_, sz;
static vector<ll> dep;
static int timer_;
static Seg seg;
void dfs_hld(int u, int p){
parent_[u] = p;
sz[u] = 1;
for(auto &ed : g[u]){
int v = ed.first; int w = ed.second;
if(v == p) continue;
dep[v] = dep[u] + (ll)w;
dfs_hld(v, u);
sz[u] += sz[v];
}
}
void hld_build(int u, int p){
int heavy = -1;
for(auto &ed : g[u]){
int v = ed.first;
if(v == p) continue;
if(heavy == -1 || sz[v] > sz[heavy]) heavy = v;
}
// assign id
timer_++;
id_[u] = timer_;
id_rev[timer_] = u;
if(heavy != -1){
head[heavy] = head[u];
hld_build(heavy, u);
}
for(auto &ed : g[u]){
int v = ed.first;
if(v == p || v == heavy) continue;
head[v] = v;
hld_build(v, u);
}
}
// helper: sum of enabled edges on chain head..x
// note: edges are represented by positions id[node]; the edge parent->node sits at id[node] (root has no edge)
inline ll chain_sum_edges(int h_id, int x_id){
// edges on path from node with id h_id to node with id x_id are positions (h_id+1 .. x_id)
if(h_id + 1 > x_id) return 0;
return seg.range_sum(h_id + 1, x_id);
}
// up(x): find top-most node of the component containing x when edges marked =1
int up_node(int x){
// if the node itself has no edges upward (i.e., path empty), we may return it
while(true){
int h = head[x];
int hid = id_[h];
int xid = id_[x];
ll total = chain_sum_edges(hid, xid);
if(total == (ll)(xid - hid)){
// whole chain from h..x is filled; try go above
if(parent_[h] == -1) return h;
x = parent_[h];
continue;
} else {
// binary search within [hid, xid] to find minimal pos pos such that edges pos+1..xid are all ones
int L = hid, R = xid;
while(L < R){
int M = (L + R) >> 1;
ll s = chain_sum_edges(M, xid);
if(s == (ll)(xid - M)) R = M;
else L = M + 1;
}
return id_rev[L];
}
}
}
// set all edges on path from root of chain to node x to value val (0 or 1)
void set_path_up(int x, int val){
while(true){
int h = head[x];
int hid = id_[h];
int xid = id_[x];
if(hid + 1 <= xid) seg.range_assign(hid+1, xid, val);
if(parent_[h] == -1) break;
x = parent_[h];
}
}
// API functions required by grader
void Init(int N, int A[], int B[], int D[]){
Nglob = N;
g.clear(); g.resize(Nglob);
id_.assign(Nglob, 0);
id_rev.assign(Nglob+1, 0); // 1-based ids -> id_rev[1..N]
head.assign(Nglob, 0);
parent_.assign(Nglob, -1);
sz.assign(Nglob, 0);
dep.assign(Nglob, 0);
timer_ = 0;
// A,B,D length N-1
for(int i = 0; i < Nglob - 1; ++i){
int a = A[i], b = B[i], d = D[i];
// assume input nodes are 0-based as in JOI spec
g[a].push_back({b, d});
g[b].push_back({a, d});
}
// root at 0
dep[0] = 0;
parent_[0] = -1;
dfs_hld(0, -1);
head[0] = 0;
hld_build(0, -1);
// seg tree size = N (we use positions 1..N)
seg.init(Nglob);
}
long long Query(int S, int X[], int T, int Y[]){
// mark all chains from each X[i] to top (set edges = 1)
for(int i = 0; i < S; ++i){
int v = X[i];
set_path_up(v, 1);
}
// for each Y find its top-most node u and distance from Y to u
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);
}
// unmark X chains (restore edges = 0)
for(int i = 0; i < S; ++i){
int v = X[i];
set_path_up(v, 0);
}
// reduce vs to minimal per u
unordered_map<int,ll> best;
best.reserve(vs.size()*2+5);
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;
}
ll ans = LLONG_MAX;
for(int i = 0; i < S; ++i){
int x = X[i];
int u = up_node(x);
auto it = best.find(u);
if(it == best.end()) continue;
ll cand = (dep[x] - dep[u]) + it->second;
if(cand < ans) ans = cand;
}
if(ans == LLONG_MAX) return -1; // if unreachable; problem statement may guarantee reachable, adapt if needed
return ans;
}
