#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=500050;
const int L=25;
vector<pair<int,int>> E[N];
int par[N][L],dep[N];
ll sum[N];
void DFS(int u,int p){
dep[u]=dep[p]+1;
par[u][0]=p;
for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
for(auto e:E[u])if(e.first!=p){
sum[e.first]=sum[u]+e.second;
DFS(e.first,u);
}
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
return u==v?v:par[u][0];
}
ll Dist(int u,int v){return sum[u]+sum[v]-2*sum[LCA(u,v)];}
int sz[N];
bool was[N];
void DFSSZ(int u,int p){sz[u]=1;for(auto e:E[u])if(!was[e.first]&&e.first!=p)DFSSZ(e.first,u),sz[u]+=sz[e.first];}
int Find(int u,int p,int n){for(auto e:E[u])if(!was[e.first]&&e.first!=p&&sz[e.first]*2>n)return Find(e.first,u,n);return u;}
int Find(int u){DFSSZ(u,u);u=Find(u,u,sz[u]);was[u]=true;return u;}
vector<int> up[N];
void Update(int u,int p,int st){
up[u].pb(st);
for(auto e:E[u])if(e.first!=p&&!was[e.first])Update(e.first,u,st);
}
void Decompose(int u){
u=Find(u);
Update(u,u,u);
for(auto e:E[u])if(!was[e.first])Decompose(e.first);
}
bool have[N];
ll dist[N];
void Init(int n,int a[],int b[],int d[]){
for(int i=0;i<n-1;i++){
a[i]++;b[i]++;
E[a[i]].pb({b[i],d[i]});
E[b[i]].pb({a[i],d[i]});
}
DFS(1,0);
Decompose(1);
for(int i=0;i<n;i++)dist[i]=1e18;
}
ll Query(int s,int x[],int t,int y[]){
for(int i=0;i<s;i++){
x[i]++;
for(int u:up[x[i]])dist[u]=min(dist[u],Dist(x[i],u)),have[u]=true;
}
ll ans=1e18;
for(int i=0;i<t;i++){
y[i]++;
for(int u:up[y[i]])ans=min(ans,dist[u]+Dist(y[i],u));
}
for(int i=0;i<s;i++)for(int u:up[x[i]])dist[u]=1e18,have[u]=false;
return ans;
}
