#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;
vector<vector<pii>> g;
vector<int> sz;
vector<bool> used;
void fill_sz(int v, int pr){
sz[v] = 1;
for (auto [i, w]: g[v]){
if (i == pr || used[i]) continue;
fill_sz(i, v);
sz[v] += sz[i];
}
}
int find(int v, int pr, int& S){
for (auto [i, w]: g[v]){
if (i == pr || used[i]) continue;
if (2 * sz[i] >= S){
return find(i, v, S);
}
}
return v;
}
vector<vector<ll>> dist;
vector<int> dd, P;
void fill_dist(int v, int pr, int& k){
for (auto [i, w]: g[v]){
if (i == pr || used[i]) continue;
dist[k][i] = dist[k][v] + w;
fill_dist(i, v, k);
}
}
void arvid(int v, int k){
fill_sz(v, 0);
v = find(v, 0, sz[v]);
P[v] = k; used[v] = 1;
dd[v] = dd[k] + 1;
fill_dist(v, 0, dd[v]);
for (auto [i, w]: g[v]){
if (!used[i]){
arvid(i, v);
}
}
}
vector<ll> f;
void Init(int n, vector<int> a, vector<int> b, vector<int> w){
g.resize(n + 1);
for (int i = 0; i < n - 1; i++){
a[i]++; b[i]++;
g[a[i]].pb({b[i], w[i]});
g[b[i]].pb({a[i], w[i]});
}
sz.resize(n + 1);
dd.resize(n + 1);
used.resize(n + 1);
P.resize(n + 1);
dist.resize(log2(n) + 1);
for (int i = 0; i <= log2(n); i++){
dist[i].resize(n + 1);
}
dd[0] = -1; arvid(1, 0);
f.assign(n + 1, inf);
}
vector<int> rem;
ll Query(int s, vector<int> x, int t, vector<int> y){
rem.clear();
for (int i = 0; i < s; i++){
int v = ++x[i];
while (v > 0){
f[v] = min(f[v], dist[dd[v]][x[i]]);
rem.pb(v);
v = P[v];
}
}
ll out = inf;
for (int i = 0; i < t; i++){
int v = ++y[i];
while (v > 0){
out = min(out, dist[dd[v]][y[i]] + f[v]);
v = P[v];
}
}
for (int i: rem) f[i] = inf;
return out;
}
