#include "factories.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll KP=1e6+100,NP=1e6+100,lg=22;
ll n,in[KP];
bool iny[KP];
vector<pair<ll,ll>> ma[KP];
ll h[KP],mi[NP][lg];
vector<ll> ord;
void dfs(ll x,ll p=-1)
{
in[x]=ord.size();
ord.push_back(x);
for(auto y:ma[x])
{
if(y.second!=p)
{
h[y.second]=h[x]+y.first;
dfs(y.second,x);
ord.push_back(x);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
ord.clear();
for(ll i=0;i<=n;i++)h[i]=0,ma[i].clear();
for(ll i=0;i<n-1;i++)
{
ma[A[i]].push_back({D[i],B[i]});
ma[B[i]].push_back({D[i],A[i]});
}
dfs(0);
// cout<<"ORD: ";
// for(auto x:ord)cout<<x<<' ';
// cout<<endl;
// cout<<"Hei: ";
for(ll i=0;i<ord.size();i++)
{
mi[i][0]=h[ord[i]];
// cout<<h[ord[i]]<<' ';
}
// cout<<endl;
for(ll j=1;j<lg;j++)
{
for(ll i=0;i+(1<<j)-1<ord.size();i++)
{
mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
}
// cout<<ord.size()<<endl;
// ord.size() = 2*n-1
}
ll dist(ll x,ll y)
{
if(x>y)swap(x,y);
// [x,y]
ll lp=__lg(y-x+1);
return min(mi[x][lp],mi[y-(1<<lp)+1][lp]);
}
const ll SQT=707;
ll d[KP];
long long Query(int S, int X[], int T, int Y[]) {
ll ans=1e18;
if(S<SQT)
{ // SQT * 1e6
for(ll i=0;i<S;i++)
{
ll x=X[i];
for(ll j=0;j<T;j++)
{
ll y=Y[j];
ans=min(ans,h[x]+h[y]-2*dist(in[x],in[y]));
}
}
}
else
{ // n * lg n * 1e6/SQT
// multi-source Dykstra
// O(2nlgn)
priority_queue<pair<ll,ll>> pq;
for(ll i=0;i<n;i++)
{
d[i]=1e9;
iny[i]=0;
}
for(ll i=0;i<T;i++)
{
iny[Y[i]]=1;
}
for(ll i=0;i<S;i++)
{
d[X[i]]=0;
pq.push({0,X[i]});
}
while(pq.size())
{
auto it=pq.top();
pq.pop();
ll x=it.second;
ll dt=it.first;
if(iny[x])
{
return -dt;
}
if(-dt!=d[x])continue;
for(auto y:ma[x])
{
ll yp=y.second,w=y.first;
if(d[yp]>(w-dt))
{
d[yp]=w-dt;
pq.push({dt-w,yp});
}
}
}
}
return ans;
}
