#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define int long long
const int N = 5e5 + 20;
const int LOG = 20;
vector<ar<int,2>> g[N];
int d[N];
int dep[N];
int up[N][LOG];
void chmin(int &x,int y){
x = min(x, y);
}
void dfs(int x,int p){
up[x][0] = p;
for(int i = 1;i < LOG;i++)up[x][i] = up[up[x][i - 1]][i - 1];
for(auto [u, w]: g[x]){
if(u == p)continue;
d[u] = d[x] + w;
dep[u] = dep[x] + 1;
dfs(u, x);
}
}
int lca(int a,int b){
if(dep[a] < dep[b])swap(a, b);
int k = dep[a] - dep[b];
for(int i = 0;i < LOG;i++){
if((1 << i) & k)a = up[a][i];
}
if(a == b)return a;
for(int i = LOG - 1;i >= 0;i--){
if(up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
int qry(int a, int b){
int l = lca(a, b);
return d[a] + d[b] - 2 * d[l];
}
bool del[N];
int par[N];
int sz[N];
int dfs1(int x,int p){
sz[x] = 1;
for(auto [u, w]: g[x]){
if(u == p || del[u])continue;
sz[x] += dfs1(u, x);
}
return sz[x];
}
int C(int x,int p,int s){
for(auto [u, w]: g[x]){
if(u == p || del[u])continue;
if(sz[u] > s)return C(u, x, s);
}
return x;
}
void cc(int x,int p){
int s = dfs1(x, x);
x = C(x, x, s / 2);
del[x] = 1;
par[x] = p;
for(auto [u, w]: g[x]){
if(del[u])continue;
cc(u, x);
}
}
int mn[N];
int nn;
void Init(signed n, signed A[], signed B[], signed D[]) {
nn = n;
for(int i = 0;i < n - 1;i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
cc(0, -1);
// for(int i = 0;i < n;i++)cout<<par[i]<<" ";
//cout<<'\n';
// cout<<"what"<<lca(1, 6)<<'\n';
for(int i = 0;i < n;i++)mn[i] = 1e17;
//assert(0);
}
long long Query(signed n, signed X[], signed m, signed Y[]) {
set<int> s;
for(int i = 0;i < n;i++){
int x = X[i];
//cout<<"AA: ";
while(x != -1){
// cout<<x<<" ";
s.insert(x);
chmin(mn[x], qry(x, X[i]));
x = par[x];
}
//cout<<'\n';
}
// for(int i = 0;i < nn;i++)cout<<mn[i]<<" ";
// cout<<'\n';
int ans = 1e17;
for(int i = 0;i < m;i++){
int x = Y[i];
// cout<<"AA: ";
while(x != -1){
// cout<<x<<" ";
chmin(ans, mn[x] + qry(x, Y[i]));
x = par[x];
}
// cout<<'\n';
}
for(auto u: s)mn[u] = 1e17;
return ans;
}
#define int signed
