#include "factories.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 510'010;
const int lg = 19;
vector<pll> A0[N];
vector<int> ord;
int rmq[lg+1][2*N];
int st[N], ft[N], h[N];
ll dis[N];
int n;
void dfs(int v, int p, ll d, int h)
{
::h[v] = h;
st[v] = ord.size();
ord.push_back(v);
dis[v] = d;
for (auto [u, w] : A0[v]) {
if (u != p) {
dfs(u, v, d + w, h+1);
ord.push_back(v);
}
}
ft[v] = ord.size();
}
#define HMIN(x, y) (h[x]<h[y]?(x):(y))
void rmq_init()
{
int n = ord.size();
Loop (i,0,n)
rmq[0][i] = ord[i];
{ vector<int> dard; ord.swap(dard); }
Loop (i,0,lg)
for (int j = 0; j + (2<<i) <= n; ++j)
rmq[i+1][j] = HMIN(rmq[i][j], rmq[i][j+(1<<i)]);
}
pair<ll,int> get_dis(int x, int y)
{
ll ans = dis[x] + dis[y];
if (st[x] > st[y]) {
int tmp = x;
x = y;
y = tmp;
}
x = st[x];
y = st[y]+1;
int l = __lg(y - x);
int a = HMIN(rmq[l][x], rmq[l][y - (1<<l)]);
ans -= 2*dis[a];
return {ans, a};
}
void Init(int N, int X[], int Y[], int D[])
{
n = N;
Loop (i,0,n) {
A0[X[i]].push_back({Y[i],D[i]});
A0[Y[i]].push_back({X[i],D[i]});
}
dfs(0, 0, 0, 0);
rmq_init();
Loop (i,0,N) {
vector<pll> dard;
A0[i].swap(dard);
}
}
ll dij(const vector<vector<pll>> &A, const vector<int> &x, const vector<int> &y)
{
static ll dis[N];
fill(dis, dis+A.size(), (ll)1e18);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
for (int v : x) {
dis[v] = 0;
q.push({0,v});
}
while (q.size()) {
auto [d, v] = q.top();
q.pop();
if (d != dis[v])
continue;
for (auto [u, w] : A[v]) {
if (d + w < dis[u]) {
dis[u] = d + w;
q.push({dis[u], u});
}
}
}
ll ans = 1e18;
for (int v : y)
ans = min(ans, dis[v]);
return ans;
}
long long Query(int S, int X[], int T, int Y[])
{
static bool imp_vis[N];
vector<tuple<int,int,int>> imp;
Loop (i,0,S) {
imp_vis[X[i]] = 1;
imp.push_back({st[X[i]], X[i], 1});
}
Loop (i,0,T) {
imp_vis[Y[i]] = 1;
imp.push_back({st[Y[i]], Y[i], 2});
}
if (!imp_vis[0]) {
imp_vis[0] = 1;
imp.push_back({0, 0, 0});
}
sort(imp.begin(), imp.end());
int kooft_ = imp.size();
Loop (i,1,kooft_) {
int v = get_dis(get<1>(imp[i]), get<1>(imp[i-1])).second;
if (!imp_vis[v]) {
imp_vis[v] = 1;
imp.push_back({st[v], v, 0});
}
}
sort(imp.begin(), imp.end());
vector<int> stk = {0};
vector<vector<pll>> A(imp.size());
Loop (i,1,imp.size()) {
int v = get<1>(imp[i]);
while (ft[get<1>(imp[stk.back()])] <= st[v])
stk.pop_back();
int d = get_dis(get<1>(imp[stk.back()]), v).first;
A[stk.back()].push_back({i, d});
A[i].push_back({stk.back(), d});
stk.push_back(i);
}
vector<int> vec2[3];
Loop (i,0,imp.size())
vec2[get<2>(imp[i])].push_back(i);
for (auto [_, v, __] : imp)
imp_vis[v] = 0;
return dij(A, vec2[1], vec2[2]);
}
