#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const ll MXN = 5e5 + 20 , LOG = 20 , Inf = 1e17;
vector<pair<ll,ll>> adj[MXN] , virt[MXN];
ll sz[MXN] , h[MXN] , wg[MXN] , sttime[MXN] , par[LOG][MXN] , tme;
ll dis[MXN];
bool mark[MXN];
bool in_subtree(int v , int u) {
return sttime[v] >= sttime[u] && sttime[v] < sttime[u] + sz[u];
}
void prep(int v , int dad , ll dadw) {
sttime[v] = tme++;
sz[v] = 1;
h[v] = (dad == -1 ? 0 : h[dad]+1);
wg[v] = (dad == -1 ? 0 : wg[dad] + dadw);
par[0][v] = (dad == -1 ? v : dad);
for(auto pr : adj[v]) {
ll u = pr.first , w = pr.second;
if(u == dad) continue;
prep(u , v , w);
sz[v] += sz[u];
}
}
int kth_anc(int v , int k) {
while(k > 0) {
int x = __builtin_ctz(k);
v = par[x][v];
k -= (1 << x);
}
return v;
}
int LCA(int v , int u) {
if(h[v] > h[u]) swap(v , u);
u = kth_anc(u , h[u]-h[v]);
if(v == u) return v;
for(int i = LOG-1 ; i >= 0 ; i--) {
if(par[i][v] != par[i][u]) {
v = par[i][v]; u = par[i][u];
}
}
return par[0][v];
}
void Init(int n , int v[] , int u[] , int w[]) {
for(int i = 0 ; i < n-1 ; i++) {
adj[v[i]].push_back({u[i] , w[i]});
adj[u[i]].push_back({v[i] , w[i]});
}
prep(0 , -1 , 0);
for(int i = 1 ; i < LOG ; i++) {
for(int j = 0 ; j < n ; j++) {
par[i][j] = par[i-1][par[i-1][j]];
}
}
}
long long Query(int s , int X[] , int t , int Y[]) {
vector<int> A(s) , B(t) , V;
for(int i = 0 ; i < s ; i++) {
A[i] = X[i]; V.push_back(A[i]);
}
for(int i = 0 ; i < t ; i++) {
B[i] = Y[i]; V.push_back(B[i]);
}
sort(V.begin() , V.end() , [&](int a , int b) {
return sttime[a] < sttime[b];
});
int c = V.size();
for(int i = 0 ; i < c-1 ; i++) {
V.push_back(LCA(V[i] , V[i+1]));
}
sort(V.begin() , V.end() , [&](int a , int b) {
return sttime[a] < sttime[b];
});
V.resize(unique(V.begin() , V.end())-V.begin());
vector<int> stck;
for(auto v : V) {
while(stck.size() > 0 && !in_subtree(v , stck.back())) stck.pop_back();
if(stck.size() > 0) {
virt[stck.back()].push_back({v , wg[v]-wg[stck.back()]});
virt[v].push_back({stck.back() , wg[v]-wg[stck.back()]});
}
stck.push_back(v);
}
set<pair<ll,ll>> st;
for(auto v : V) dis[v] = Inf;
for(auto v : A) {
dis[v] = 0; st.insert({0 , v});
}
while(!st.empty()) {
pair<ll,ll> p = *st.begin(); st.erase(p);
ll v = p.second; mark[v] = 1;
for(auto pr : virt[v]) {
ll u = pr.first , w = pr.second;
if(mark[u]) continue;
st.erase({dis[u] , u});
dis[u] = min(dis[u] , dis[v] + w);
st.insert({dis[u] , u});
}
}
ll ans = Inf;
for(auto v : B) {
ans = min(ans , dis[v]);
}
for(auto v : V) {
virt[v].clear();
dis[v] = 0;
mark[v] = 0;
}
return ans;
}
