#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define in array<ll, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 5e5+5;
const int LOGM = 19;
const ll INF = 1e18;
vector<ll> d(MX, INF);
vector<in> adj[MX], edge[MX];
int pa[LOGM][MX];
int tin[MX], tout[MX];
ll dep[MX];
int timer;
void dfs(int u, ll lvl)
{
tin[u] = ++timer;
dep[u] = lvl;
for(int i = 1; i < LOGM; i++)
pa[i][u] = pa[i-1][pa[i-1][u]];
for(auto [v, w]: adj[u])
{
if(v == pa[0][u])
continue;
pa[0][v] = u;
dfs(v, lvl+w);
}
tout[u] = timer;
return;
}
int lca(int u, int v)
{
if(tin[u] >= tin[v])
swap(u, v);
if(tout[u] >= tout[v])
return u;
for(int i = LOGM-1; i >= 0; i--)
{
int p = pa[i][u];
if(tout[p] >= tout[v])
continue;
u = p;
}
return pa[0][u];
}
void Init(int n, int a[], int b[], int d[])
{
for(int i = 0; i < n-1; i++)
{
adj[a[i]+1].pb({b[i]+1, d[i]});
adj[b[i]+1].pb({a[i]+1, d[i]});
}
timer = 0;
tin[0] = -1; tout[0] = n+1;
pa[0][0] = 0; pa[0][1] = 0;
dfs(1, 0);
return;
}
ll Query(signed a, signed X[], signed b, signed Y[])
{
for(int i = 0; i < a; i++)
X[i]++;
for(int i = 0; i < b; i++)
Y[i]++;
priority_queue<in> pq;
vector<in> vv;
for(int i = 0; i < a; i++)
{
d[X[i]] = 0;
pq.push({0ll, X[i]});
vv.pb({tin[X[i]], X[i]});
}
for(int i = 0; i < b; i++)
vv.pb({tin[Y[i]], Y[i]});
sort(vv.begin(), vv.end());
for(int i = 1; i < (a+b); i++)
{
int w = lca(vv[i][1], vv[i-1][1]);
vv.pb({tin[w], w});
}
vector<int> path;
sort(vv.begin(), vv.end()); path.pb(vv[0][1]);
for(int i = 1; i < vv.size(); i++)
{
while(tout[path.back()] < tout[vv[i][1]])
path.pob();
int u = path.back();
int v = vv[i][1];
path.pb(v);
edge[u].pb({v, dep[v]-dep[u]});
edge[v].pb({u, dep[v]-dep[u]});
}
while(pq.size())
{
auto [W, u] = pq.top(); W = -W;
pq.pop();
if(d[u] < W)
continue;
for(auto [v, w]: edge[u])
{
if(d[v] > (d[u] + w))
{
d[v] = d[u] + w;
pq.push({-d[v], v});
}
}
}
ll ans = 1e18;
for(int i = 0; i < b; i++)
ans = min(ans, d[Y[i]]);
for(auto [t, W]: vv)
{
d[W] = INF;
edge[W].clear();
}
return ans;
}
