#pragma GCC optimize("Ofast")
#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const ll INF = 1e18;
const int MAXN = (int)5e5 + 5;
const int MAXQ = (int)1e5 + 5;
const int L = 19;
vector <pii> g[MAXN];
int n;
bool used[MAXN];
int sub[MAXN];
vector <int> G[MAXN];
int Gpar[MAXN];
ll opt[MAXN];
ll d[MAXN];
pii arr[MAXN];
int ind = 1;
pii bound[MAXN];
struct Sparse_Table {
pii tb[MAXN * 2][L + 1];
int lg[MAXN * 2];
Sparse_Table () {
}
pii merge(pii a, pii b) {
if (a.sc < b.sc) {
return a;
} else {
return b;
}
}
void build(int n) {
lg[1] = 0;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
for (int pw = 0; pw <= L; pw++) {
for (int i = 1; i <= n; i++) {
if (pw == 0) {
tb[i][pw] = arr[i];
}
else if (i + (1 << pw) - 1 <= n) {
tb[i][pw] = merge(tb[i][pw - 1], tb[i + (1 << (pw - 1))][pw - 1]);
}
}
}
}
int get_lca(int a, int b) {
int l = min(bound[a].fr, bound[b].fr);
int r = max(bound[a].sc, bound[b].sc);
int sz = lg[r - l + 1];
pii lca = merge(tb[l][sz], tb[r - (1 << sz) + 1][sz]);
return lca.fr;
}
}Tree;
void precalc(int v, int par, int dep = 0, ll len = 0) {
arr[ind++] = {v, dep};
d[v] = len;
for (auto [to, dist] : g[v]) {
if (to != par) {
precalc(to, v, dep + 1, len + dist);
arr[ind++] = {v, dep};
}
}
}
ll get_dist(int a, int b) {
int lca = Tree.get_lca(a, b);
return d[a] + d[b] - (d[lca] << 1);
}
void calc(int v, int par) {
sub[v] = 1;
for (auto [to, dist] : g[v]) {
if (to != par && !used[to]) {
calc(to, v);
sub[v] += sub[to];
}
}
}
int find_centroid(int v, int par, int sz) {
for (auto [to, dist] : g[v]) {
if (to != par && sub[to] > (sz >> 1) && !used[to]) {
return find_centroid(to, v, sz);
}
}
return v;
}
void build(int v, int par) {
calc(v, -1);
int center = find_centroid(v, -1, sub[v]);
used[center] = 1;
if (par != -1) {
G[center].pb(par);
G[par].pb(center);
Gpar[center] = par;
}
for (auto [to, dist] : g[center]) {
if (!used[to]) {
build(to, center);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
memset(Gpar, -1, sizeof(Gpar));
fill(opt, opt + MAXN, INF);
n = N;
for (int i = 0; i < n - 1; i++) {
int u = A[i];
int v = B[i];
int dist = D[i];
g[u].pb({v, dist});
g[v].pb({u, dist});
}
precalc(0, -1);
for (int i = 0; i < n; i++) {
bound[i] = {1e9, -1e9};
}
for (int i = 1; i < ind; i++) {
int v = arr[i].fr;
chmin(bound[v].fr, i);
chmax(bound[v].sc, i);
}
Tree.build(ind - 1);
build(0, -1);
}
void upd(int v, int type) {
if (type == 1) {
int cur = v;
while (1) {
if (cur == -1) {
break;
}
opt[cur] = min(opt[cur], get_dist(cur, v));
cur = Gpar[cur];
}
}
else {
int cur = v;
while (1) {
if (cur == -1) {
break;
}
opt[cur] = INF;
cur = Gpar[cur];
}
}
}
ll get(int v) {
ll ret = INF;
int cur = v;
while (1) {
if (cur == -1) {
break;
}
ret = min(ret, get_dist(v, cur) + opt[cur]);
cur = Gpar[cur];
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = INF;
for (int i = 0; i < S; i++) {
upd(X[i], 1);
}
for (int i = 0; i < T; i++) {
ans = min(ans, get(Y[i]));
}
for (int i = 0; i < S; i++) {
upd(X[i], -1);
}
return ans;
}
