#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int par[19][500005], depth[500005], mp[500005], cnt, sz;
vector<pair<int, long long> > adj[500005];
priority_queue<pair<long long, int> > pq;
long long dist[500005], d[500005];
bool visited[500005];
vector<int> vec;
int lca(int u, int v)
{
if (depth[u]>depth[v])
swap(u, v);
int cur=depth[v]-depth[u];
for (int i=18; i>=0; i--)
if (cur&(1<<i))
v=par[i][v];
if (u==v)
return u;
for (int i=18; i>=0; i--)
{
if (par[i][u]!=par[i][v])
{
u=par[i][u];
v=par[i][v];
}
}
return par[0][u];
}
void dfs(int u, int p, long long dis, int dep)
{
mp[u]=cnt;
cnt++;
par[0][mp[u]]=mp[p];
dist[mp[u]]=dis;
depth[mp[u]]=dep;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
long long w=adj[u][i].second;
if (v!=p)
dfs(v, u, dis+w, dep+1);
}
}
void dfs2(int ind)
{
int u=vec[ind];
while (cnt<sz && lca(u, vec[cnt])==u)
{
int v=vec[cnt];
long long w=dist[v]-dist[u];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
cnt++;
dfs2(cnt-1);
}
}
void Init(int N, int A[], int B[], int D[])
{
for (int i=0; i<=N-2; i++)
{
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0, 0);
for (int i=1; i<=18; i++)
for (int j=0; j<N; j++)
par[i][j]=par[i-1][par[i-1][j]];
for (int i=0; i<N; i++)
adj[i].clear();
}
long long Query(int S, int X[], int T, int Y[])
{
vec.clear();
for (int i=0; i<S; i++)
{
X[i]=mp[X[i]];
vec.push_back(X[i]);
}
for (int i=0; i<T; i++)
{
Y[i]=mp[Y[i]];
vec.push_back(Y[i]);
}
sort(vec.begin(), vec.end());
for (int i=1; i<S+T; i++)
vec.push_back(lca(vec[i-1], vec[i]));
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end())-vec.begin());
sz=vec.size();
cnt=1;
dfs2(0);
for (int i=0; i<sz; i++)
{
d[vec[i]]=1e18;
visited[vec[i]]=0;
}
for (int i=0; i<S; i++)
{
d[X[i]]=0;
pq.push({0, X[i]});
}
while (!pq.empty())
{
int u=pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u]=1;
for (int i=0; i<adj[u].size(); i++)
{
int v=adj[u][i].first;
long long w=adj[u][i].second;
if (d[v]>d[u]+w)
{
d[v]=d[u]+w;
pq.push({-d[v], v});
}
}
}
long long ans=1e18;
for (int i=0; i<T; i++)
ans=min(ans, d[Y[i]]);
for (int i=0; i<sz; i++)
adj[vec[i]].clear();
return ans;
}
