#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 600000, K = 22, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
int order[N], timeStamp;
int par[N];
int dpar[N];
void dfs(int u, int p, i64 d = 0){
order[timeStamp++] = u;
par[u] = p;
P[u] = timer;
pos[timer++] = d;
D[u] = d;
for (auto [v, w] : e[u]) {
if (v != p) {
dpar[v] = w;
dfs(v, u, d + w);
pos[timer++] = d;
}
}
}
inline i64 dist(int u, int v) {
int L = P[u], R = P[v];
if (L > R) std::swap(L, R);
int j = lg[R - L + 1];
return D[u] + D[v] - std::min(st[j][L], st[j][R - (1 << j) + 1]);
}
void Init(int n, int A[], int B[], int D[]) {
lg[1] = 0;
for (int i = 2; i <= M; i++)
lg[i] = lg[i / 2] + 1;
::n = n;
for (int i = 0; i < n - 1; i++) {
e[A[i]].emplace_back(B[i], D[i]);
e[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, 0);
for (int i = 0; i < M; i++)
st[0][i] = 2 * pos[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= M; i++)
st[j][i] = std::min(st[j-1][i], st[j - 1][i + (1 << (j - 1))]);
}
i64 dp[N];
i64 Query(int S, int X[], int T, int Y[]) {
if (S + T <= 3050) {
i64 ans = 1e16;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = std::min(ans, dist(X[i], Y[j]));
}
}
return ans;
}
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < S; i++) {
dp[X[i]] = 0;
}
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
dp[par[u]] = std::min(dp[par[u]], dp[u] + dpar[u]);
}
for (int i = 0; i < n; i++) {
int u = order[i];
dp[u] = std::min(dp[u], dp[par[u]] + dpar[u]);
}
i64 ans = 1e16;
for (int i = 0; i < T; i++) {
ans = std::min(ans, dp[Y[i]]);
}
return ans;
}
