#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<pair<long long int,long long int>>g[500000],cd[500000],v(500000);
vector<int>sz(500000);
int m=1;
bool vis[500000]={0};
void dfs(int a,int b)
{
sz[a]=1;
for(auto p:g[a])
{
int i=p.first;
if(i!=b&&vis[i]==0)
{
dfs(i,a);
sz[a]+=sz[i];
}
}
}
void dfs2(int a,int b,long long int d,int k)
{
cd[a].push_back({k,d});
for(auto p:g[a])
{
int i=p.first;
if(i!=b&&vis[i]==0)
{
dfs2(i,a,d+p.second,k);
}
}
}
void cen(int a)
{
dfs(a,a);
int n=sz[a],b=a;
bool check=true;
while(check)
{
check=false;
for(auto p:g[a])
{
int i=p.first;
if(i!=b&&vis[i]==0&&sz[i]*2>n)
{
check=true;
b=a;
a=i;
break;
}
}
}
dfs2(a,a,0,a);
vis[a]=1;
for(auto p:g[a])
{
if(!vis[p.first])
{
cen(p.first);
}
}
}
void Init(int n, int a[], int b[], int c[])
{
for(int i=0;i<n-1;i++)
{
g[a[i]].push_back({b[i],c[i]});
g[b[i]].push_back({a[i],c[i]});
}
cen(0);
}
long long Query(int n1, int X[], int n2, int Y[])
{
for(int i=0;i<n1;i++)
{
int a=X[i];
for(int j=cd[a].size()-1;j>=0;j--)
{
auto p=cd[a][j];
if(v[p.first].first!=m+1)
{
v[p.first].second=p.second;
v[p.first].first=m+1;
}
else
{
v[p.first].second=min(v[p.first].second,p.second);
}
}
}
long long ans=50000000000000;
for(int i=0;i<n2;i++)
{
int a=Y[i];
for(int j=cd[a].size()-1;j>=0;j--)
{
auto p=cd[a][j];
if(v[p.first].first!=m+1)continue;
else ans=min(ans,v[p.first].second+p.second);
}
}
m++;
return ans;
}
