#include "factories.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define N 500020
#define pb push_back
#define logn 20
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
using namespace std;
typedef pair<ll, ll> pii;
typedef vector<int> vi;
vector<pii> grafo[N];
int n, q, in[N];
struct edge{
int a, b;
ll c;
};
struct binarylift{
int anc[N][logn], deep[N], cnt;
ll distt[N];
void dfs(int x, int p){
in[x] = ++cnt;
anc[x][0] = p;
deep[x] = deep[p] + 1;
for(auto v: grafo[x]){
if(v.f == p) continue;
distt[v.f] =distt[x] + 1LL*v.s;
dfs(v.f, x);
}
}
int lca(int u, int v){
if(deep[v] > deep[u]) swap(u, v);
for(int i = logn - 1; i>=0; i--)
if(deep[u] - (1<<i) >= deep[v]) u = anc[u][i];
if(u == v){
return u;
}
for(int i = logn - 1; i>=0; i--)
if(anc[u][i] != -1 & anc[u][i] != anc[v][i]){
u = anc[u][i];
v = anc[v][i];
}
return anc[u][0];
}
void solve(){
memset(anc, -1, sizeof anc);
dfs(1, 1);
for(int j = 1; j < logn; j++)
for(int i = 1; i <= n; i++)
anc[i][j] = anc[anc[i][j-1]][j-1];
}
ll dist(int a, int b){
return distt[a]+distt[b]-2*distt[lca(a,b)];
}
} b;
pair<vector<edge> ,int> build_virtual_tree(vi K){
auto f = [&](int a , int b){
return in[a] < in[b];
};
vector<edge> e;
sort(all(K) , f);
int m = sz(K);
rep(i,1,m){
K.push_back(b.lca(K[i] , K[i-1]));
}
sort(all(K) , f);
K.erase(unique(all(K)) , K.end());
rep(i,0,sz(K) -1){
int z = b.lca(K[i] , K[i+1]);
e.push_back({K[i+1] , z ,b.dist(z,K[i+1])});
}
return {e ,K[0]};
}
ll dist[N];
void Init(int NN, int A[], int B[], int D[]) {
n=NN;
for(int i = 0; i < N; i++) dist[i] = (ll)(2e18);
for(int i = 0; i < n - 1; i++){
int a = A[i], b = B[i];
ll c = D[i];
a++,b++;
grafo[a].pb({b, c});
grafo[b].pb({a, c});
}
b.solve();
}
vector< pii > tree[N];
ll Query(int S, int X[], int T, int Y[]) {
vector<int> caras;
for(int i =0;i<S;i++){
X[i] ++;
caras.pb(X[i]);
}
for(int i =0;i<T;i++){
Y[i] ++;
caras.pb(Y[i]);
}
sort(all(caras));
caras.erase(unique(all(caras)), caras.end());
auto t = build_virtual_tree(caras);
for(auto w: t.f){
int a = w.a, b=w.b;
ll c=w.c;
tree[a].pb({b, c});
tree[b].pb({a, c});
caras.pb(a);
caras.pb(b);
}
const ll inf = (ll)(2e18);
priority_queue<pii, vector<pii>, greater<pii> > pq;
for(int i = 0; i < S; i++){
dist[X[i]] = 0, pq.push({0, X[i]});
}
while(!pq.empty()){
int x = pq.top().s;
ll d= pq.top().f;
pq.pop();
if(d>dist[x])continue;
for(auto v: tree[x]){
if(dist[v.f] > dist[x] + v.s){
dist[v.f] = dist[x] + v.s;
pq.push({dist[v.f], v.f});
}
}
}
ll ans = inf;
for(int i = 0; i < T; i++) ans = min(ans, dist[Y[i]]);
for(auto x: caras){
dist[x] = inf;
tree[x].clear();
}
return ans;
}
