#include <bits/stdc++.h>
#include "factories.h"
#define LINF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define el cout << '\n';
#define maxn int(5e5 + 5)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int LOG = 19;
int sz[maxn], parc[maxn];
int d[maxn], par[maxn][20];
ll f[maxn];
ll mn[maxn];
bool isc[maxn];
vector<pii> adj[maxn];
void dfs(int u, int p = -1) {
for(pii x : adj[u]) {
int v = x.fi, w = x.se;
if(v != p) {
par[v][0] = u;
d[v] = d[u] + 1;
f[v] = f[u] + w;
dfs(v, u);
}
}
}
void dfscount(int u, int p = -1) {
sz[u] = 1;
for(pii x : adj[u]) {
int v = x.fi;
if(v != p && !isc[v]) {
dfscount(v, u);
sz[u] += sz[v];
}
}
}
int centroid(int u, int n, int p = -1) {
for(pii x : adj[u]) {
int v = x.fi;
if(v != p && !isc[v] && sz[v] > (n >> 1)) return centroid(v, n, u);
}
return u;
}
void cd(int u, int p = -1) {
dfscount(u);
int c = centroid(u, sz[u]);
isc[c] = 1;
parc[c] = p;
for(pii x : adj[c]) {
int v = x.fi;
if(!isc[v]) cd(v, c);
}
}
int lca(int u, int v) {
if(d[u] < d[v]) swap(u, v);
int k = d[u] - d[v];
for(int i = LOG; i >= 0; i--) if(k >> i & 1) u = par[u][i];
if(u == v) return u;
for(int i = LOG; i >= 0; i--) if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
return par[u][0];
}
ll dist(int u, int v) {
return f[u] + f[v] - (f[lca(u, v)] << 1);
}
void Init(int N, int A[], int B[], int D[]) {
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(0, -1);
for(int i = 1; i <= LOG; i++)
for(int u = 0; u < N; u++)
par[u][i] = par[par[u][i - 1]][i - 1];
for(int i = 0; i < N; i++) parc[i] = -1;
cd(0);
memset(mn, 0x3f, sizeof mn);
}
void paint(int u) {
for(int v = u; v != -1; v = parc[v]) mn[v] = min(mn[v], dist(v, u));
}
void reset(int u) {
for(int v = u; v != -1; v = parc[v]) mn[v] = LINF;
}
ll get(int u) {
ll res = LINF;
for(int v = u; v != -1; v = parc[v]) res = min(res, dist(v, u) + mn[v]);
return res;
}
ll Query(int S, int X[], int T, int Y[]) {
ll res = LINF;
for(int i = 0; i < S; i++) paint(X[i]);
for(int i = 0; i < T; i++) res = min(res, get(Y[i]));
for(int i = 0; i < S; i++) reset(X[i]);
return res;
}
