#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
const int MAXLG = 20;
const long long INF = 1e18;
int N;
vector<pair<int,int>> G[MAXN + 10];
int cc[MAXN + 10];
int level[MAXN + 10];
long long dis[MAXLG + 10][MAXN + 10];
bool done[MAXN + 10];
int par[MAXN + 10];
void dfs(int u, int p, long long ds) {
dis[++level[u]][u] = ds;
cc[u] = 1;
for(auto e : G[u]) {
int v, d; tie(v, d) = e;
if(v == p || done[v]) continue;
dfs(v, u, ds + d);
cc[u] += cc[v];
}
}
int centroid(int u, int p, int cnt) {
for(auto e : G[u]) {
int v = e.first;
if(v == p || done[v]) continue;
if(cc[v] > cnt/2) return centroid(v, u, cnt);
}
return u;
}
void decomp(int u, int p) {
u = centroid(u, -1, cc[u]); dfs(u, -1, 0);
// cerr << "centroid = " << u << "\n";
par[u] = p;
done[u] = true;
for(auto e : G[u]) {
int v = e.first;
if(done[v]) continue;
decomp(v, u);
}
}
long long mn[MAXN + 10];
void Init(int N_, int A[], int B[], int D[]) {
N = N_;
for(int i = 0; i < N-1; i++) {
G[A[i]].emplace_back(B[i], D[i]);
G[B[i]].emplace_back(A[i], D[i]);
}
memset(level, -1, sizeof(level));
dfs(0, -1, 0);
decomp(0, -1);
std::fill(mn, mn + MAXN + 1, INF);
}
long long Query(int S, int X[], int T, int Y[]) {
// cerr << "\n\n";
for(int i = 0; i < S; i++) {
int u = X[i];
// cerr << "Xu = " << u << "\n";
for(int j = level[u]; j > 0; j--) {
mn[u] = min(mn[u], dis[j][X[i]]);
// cerr << "mn[" << u << "] = " << mn[u] << "\n";
u = par[u];
}
}
long long res = INF;
for(int i = 0; i < T; i++) {
int u = Y[i];
for(int j = level[u]; j > 0; j--) {
res = min(res, mn[u] + dis[j][Y[i]]);
u = par[u];
}
}
for(int i = 0; i < S; i++) {
int u = X[i];
for(int j = level[u]; j > 0; j--) {
mn[u] = INF;
u = par[u];
}
}
return res;
}
