#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5;
const int MAXLG = 20;
const long long INF = 1e18;
struct dat {
int v, w;
};
int N;
vector<dat> 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 dfs0(int u, int p) {
cc[u] = 1;
for(auto e : G[u]) {
if(e.v == p || done[e.v]) continue;
dfs0(e.v, u);
cc[u] += cc[e.v];
}
}
void dfs(int u, int p, long long ds) {
// cerr << u << " " << p << " " << ds << "\n";
dis[++level[u]][u] = ds;
// cerr << "dis[" << level[u] << "][" << u << "] = " << dis[level[u]][u] << "\n";
for(auto e : G[u]) {
if(e.v == p || done[e.v]) continue;
dfs(e.v, u, ds + e.w);
}
}
int cnt;
int centroid(int u, int p) {
for(auto e : G[u]) {
if(e.v == p || done[e.v]) continue;
if(cc[e.v] > cnt/2) return centroid(e.v, u);
}
return u;
}
void decomp(int u, int p) {
dfs0(u, -1); cnt = cc[u];
u = centroid(u, -1); dfs(u, -1, 0);
// cerr << "centroid = " << u << "\n";
par[u] = p;
done[u] = true;
for(auto e : G[u]) {
if(done[e.v]) continue;
decomp(e.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]].push_back(dat{B[i], D[i]});
G[B[i]].push_back(dat{A[i], D[i]});
}
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];
while(u != -1) {
mn[u] = INF;
u = par[u];
}
}
return res;
}
