#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const int MAXN = 5e5 + 5;
const ll inf = (ll)4e18;
vector<pair<int,int>> g[MAXN];
int dead[MAXN], sz[MAXN], par[MAXN];
vector<int> anc[MAXN];
vector<ll> dista[MAXN];
ll best[MAXN];
vector<int> q;
int n;
int dfs_size(int u, int p) {
sz[u] = 1;
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
sz[u] += dfs_size(v, u);
}
return sz[u];
}
int dfs_centroid(int u, int p, int total_sz) {
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
if(sz[v] > total_sz / 2) return dfs_centroid(v, u, total_sz);
}
return u;
}
void dfs_dist(int u, int p, int c, ll d) {
anc[u].pb(c);
dista[u].pb(d);
for(auto &[v, w] : g[u]) {
if(v == p || dead[v]) continue;
dfs_dist(v, u, c, d + w);
}
}
void decompose(int u, int p) {
int total_sz = dfs_size(u, 0);
int c = dfs_centroid(u, 0, total_sz);
dead[c] = 1;
par[c] = p;
dfs_dist(c, 0, c, 0);
for(auto &[v, w] : g[c]) {
if(dead[v]) continue;
decompose(v, c);
}
}
void upd(int u) {
FOR(i, 0, anc[u].size()) {
int c = anc[u][i];
ll d = dista[u][i];
if(best[c] == inf) q.pb(c);
best[c] = min(best[c], d);
}
}
ll get(int u) {
ll res = inf;
FOR(i, 0, anc[u].size()) {
int c = anc[u][i];
ll d = dista[u][i];
res = min(res, best[c] + d);
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i, 1, n + 1) {
g[i].clear();
anc[i].clear();
dista[i].clear();
dead[i] = 0;
sz[i] = 0;
par[i] = 0;
best[i] = inf;
}
FOR(i, 0, n - 1) {
int u = A[i] + 1, v = B[i] + 1, w = D[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
decompose(1, 0);
FOR(i, 1, n + 1) dead[i] = 0;
}
ll Query(int S, int A[], int T, int B[]) {
touched.clear();
FOR(i, 0, S) upd(A[i] + 1);
ll ans = inf;
FOR(i, 0, T) ans = min(ans, get(B[i] + 1));
for(auto x : touched) best[x] = inf;
return ans;
}
