#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 5e5 + 3;
const int lg = 20;
vector<pair<int, int>>g[nax];
int CT_par[nax];
int st[nax], en[nax], tt = 0;
int up[nax][lg];
long long d[nax];
int sub[nax];
void dfs(int v, int p) {
st[v] = tt++;
up[v][0] = p;
for(int j=1; j<lg; ++j) {
up[v][j] = up[up[v][j-1]][j-1];
}
for(auto [u, w] : g[v]) if(u!=p) {
d[u] = d[v] + w;
dfs(u, v);
}
en[v] = tt-1;
}
bool ban[nax];
int cdfs(int v, int p = -1) {
sub[v] = 1;
for(auto [u, w] : g[v]) if(u!=p && !ban[u]) {
sub[v] += cdfs(u, v);
}
return sub[v];
}
int get_centroid(int v, int sz, int p = -1) {
for(auto [u, w] : g[v]) if(sub[u]*2>sz && u!=p && !ban[u]) {
return get_centroid(u, sz, v);
}
return v;
}
void centroid(int v, int prevCen = -1) {
int C = get_centroid(v, cdfs(v));
CT_par[C] = prevCen;
ban[C] = 1;
for(auto [u, w] : g[C]) if(!ban[u]) {
centroid(u, C);
}
}
bool is_anc(int u, int v) {
return st[u]<=st[v] && en[u]>=en[v];
}
int getLCA(int u, int v) {
for(int j=lg-1; j>=0; --j) if(!is_anc(up[u][j], v)) {
u = up[u][j];
}
if(!is_anc(u, v)) u = up[u][0];
return u;
}
long long get_dist(int u, int v) {
int lca = getLCA(u, v);
return d[u] + d[v] - 2 * d[lca];
}
long long ans[nax];
long long mem[nax][lg];
void Init(int N, int A[], int B[], int D[]) {
for(int i=0; i<N; ++i) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, 0);
centroid(0);
for(int i=0; i<N; ++i) {
ans[i] = 1e18;
}
memset(mem, -1, sizeof mem);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0; i<S; ++i) {
int v = X[i];
int u = v;
int no = 0;
while(u!=-1) {
long long dis;
if(mem[v][no]!=-1) dis = mem[v][no];
else dis = mem[v][no] = get_dist(u, v);
ans[u] = min(ans[u], dis);
u = CT_par[u];
++no;
}
}
long long ret = 1e18;
for(int i=0; i<T; ++i) {
int v = Y[i];
int u = v;
int no = 0;
while(u!=-1) {
long long dis;
if(mem[v][no]!=-1) dis = mem[v][no];
else dis = mem[v][no] = get_dist(u, v);
ret = min(ret, ans[u] + dis);
u = CT_par[u];
++no;
}
}
for(int i=0; i<S; ++i) {
int v = X[i];
int u = v;
while(u!=-1) {
ans[u] = 1e18;
u = CT_par[u];
}
}
return ret;
}
