#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
const long long MAXN=500000,inf=10000000000000000LL;
int pod[MAXN];
long long nearest[MAXN];
bool used[MAXN];
vector<pair<int,long long>> anc[MAXN];
vector<pair<int,int>> edg[MAXN];
inline long long min1(long long a,long long b)
{
if(a>b)return b;
return a;
}
int getSubSize(int start,int f)
{
pod[start]=1;
for(auto i:edg[start])
{
if(used[i.first]||f==i.first)continue;
pod[start]+=getSubSize(i.first,start);
}
return pod[start];
}
int findCentr(int start,int f,int sz)
{
for(auto i:edg[start])
{
if(used[i.first]||f==i.first)continue;
if(pod[i.first]>sz/2)return findCentr(i.first,start,sz);
}
return start;
}
void findDist(int start,int f,int dist,int centrAnc)
{
anc[start].push_back({centrAnc,dist});
for(auto i:edg[start])
{
if(used[i.first]||f==i.first)continue;
findDist(i.first,start,dist+i.second,centrAnc);
}
}
void centrDec(int start)
{
int centr=findCentr(start,-1,getSubSize(start,-1));
used[centr]=1;
anc[centr].push_back({centr,0});
for(auto i:edg[centr])
{
if(used[i.first])continue;
findDist(i.first,-1,i.second,centr);
}
for(auto i:edg[centr])
{
if(used[i.first])continue;
centrDec(i.first);
}
}
void addNode(int n)
{
for(auto i:anc[n])
{
nearest[i.first]=min1(nearest[i.first],i.second);
}
}
long long query(int n)
{
long long ans=inf;
for(auto i:anc[n])
{
ans=min1(nearest[i.first]+i.second,ans);
}
return ans;
}
void Init(int N, int A[], int B[], int D[])
{
for(int i=0;i<N-1;i++)
{
edg[A[i]].push_back({B[i],D[i]});
edg[B[i]].push_back({A[i],D[i]});
}
centrDec(0);
for(int i=0;i<N;i++)
{
nearest[i]=inf;
}
}
long long Query(int S, int X[], int T, int Y[])
{
long long ans=inf;
for(int i=0;i<S;i++)
{
addNode(X[i]);
}
for(int i=0;i<T;i++)
{
ans=min1(ans,query(Y[i]));
}
for(int i=0;i<S;i++)
{
for(auto j:anc[X[i]])
{
nearest[j.first]=inf;
}
}
return ans;
}
