// 17:05 24/03/2026
// IDEA: Born_To_Laugh - Hughie Do
// IMPLEMENT: Gemini 3.1 Pro Preview
#include <bits/stdc++.h>
#include "factories.h"
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e18 + 7;
int n;
vector<vector<pair<int, long long>>> adj;
vector<int> parr;
vector<int> sz;
vector<bool> rem;
vector<long long> min_dist_to_X;
vector<long long> depd;
vector<int> depn;
vector<int> tin;
vector<int> eultour;
vector<vector<int>> st;
vector<int> logg2;
int timer = 0;
void dfs_lca(int u, int p, long long d, int h) {
tin[u] = timer;
eultour.push_back(u);
depd[u] = d;
depn[u] = h;
timer++;
for (auto& edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if (v != p) {
dfs_lca(v, u, d + w, h + 1);
eultour.push_back(u);
timer++;
}
}
}
void buildst() {
int m = eultour.size();
logg2.resize(m + 1);
logg2[1] = 0;
for (int i = 2; i <= m; i++) logg2[i] = logg2[i / 2] + 1;
int K = logg2[m] + 1;
st.assign(K, vector<int>(m));
for (int i = 0; i < m; i++) {
st[0][i] = eultour[i];
}
for (int j = 1; j < K; j++) {
for (int i = 0; i + (1 << j) <= m; i++) {
int u = st[j - 1][i];
int v = st[j - 1][i + (1 << (j - 1))];
st[j][i] = (depn[u] < depn[v]) ? u : v;
}
}
}
int lca(int u, int v) {
int L = tin[u];
int R = tin[v];
if (L > R) swap(L, R);
int j = logg2[R - L + 1];
int lo = st[j][L];
int hi = st[j][R - (1 << j) + 1];
return (depn[lo] < depn[hi]) ? lo : hi;
}
long long dist(int u, int v) {
return depd[u] + depd[v] - 2LL * depd[lca(u, v)];
}
void pre_dfs(int u, int p) {
sz[u] = 1;
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !rem[v]) {
pre_dfs(v, u);
sz[u] += sz[v];
}
}
}
int findcent(int u, int p, int total_nodes) {
for (auto& edge : adj[u]) {
int v = edge.first;
if (v != p && !rem[v] && sz[v] > total_nodes / 2) {
return findcent(v, u, total_nodes);
}
}
return u;
}
void buildcent(int u, int p) {
pre_dfs(u, -1);
int cent = findcent(u, -1, sz[u]);
parr[cent] = p;
rem[cent] = true;
for (auto& edge : adj[cent]) {
int v = edge.first;
if (!rem[v]) {
buildcent(v, cent);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
adj.resize(n);
parr.assign(n, -1);
sz.assign(n, 0);
rem.assign(n, 0);
min_dist_to_X.assign(n, INF);
depd.assign(n, 0);
depn.assign(n, 0);
tin.assign(n, 0);
for (int i = 0; i < n - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs_lca(0, -1, 0, 0);
buildst();
buildcent(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int u = X[i];
int curr = u;
while (curr != -1) {
min_dist_to_X[curr] = min(min_dist_to_X[curr], dist(u, curr));
curr = parr[curr];
}
}
long long ans = INF;
for (int i = 0; i < T; i++) {
int v = Y[i];
int curr = v;
while (curr != -1) {
if (min_dist_to_X[curr] != INF) {
ans = min(ans, dist(v, curr) + min_dist_to_X[curr]);
}
curr = parr[curr];
}
}
for (int i = 0; i < S; i++) {
int u = X[i];
int curr = u;
while (curr != -1) {
min_dist_to_X[curr] = INF;
curr = parr[curr];
}
}
return ans;
}
