#include "factories.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=5e5+6;
const ll inf=1e18;
vector<int> tree[mxn];
vector<ll> cost[mxn];
int subsz[mxn];
int centroidMarked[mxn];
int cpar[mxn];
ll cdist[30][mxn];
int level[mxn];
int dp[20][mxn];
ll dist[20][mxn];
int n;
ll ans[mxn];
void dfs1(int cur,int prev,ll cst)
{
level[cur]=(cur==0?1 :level[prev]+1);
dp[0][cur]=prev;
dist[0][cur]=cst;
for(int i=1;i<20;i++)
{
dp[i][cur]=dp[i-1][dp[i-1][cur]];
dist[i][cur]=dist[i-1][cur]+dist[i-1][dp[i-1][cur]];
}
for(int i=0;i<tree[cur].size();i++)
{
int v=tree[cur][i];
if(v==prev)continue;
dfs1(v,cur,cost[cur][i]);
}
}
int findLCA(int u,int v)
{
if(level[u]<level[v])swap(u,v);
int diff=level[u]-level[v];
for(int i=0;i<18;i++)if((diff>>i)&1)u=dp[i][u];
if(u==v)return u;
for(int i=19;i>=0;i--)
{
if(dp[i][u]!=dp[i][v]){
u=dp[i][u];
v=dp[i][v];
}
}
return dp[0][u];
}
ll getDist(int u,int v)
{
if(u==v)return 0;
if(level[u]<level[v])swap(u,v);
int diff=level[u]-level[v];
ll sum=0;
for(int i=0;i<20;i++)
{
if((diff>>i)&1)
{
sum+=dist[i][u];
u=dp[i][u];
}
}
return sum;
}
void dfs(int cur,int prev)
{
subsz[cur]=1;
for(auto i:tree[cur])
{
if(i!=prev && !centroidMarked[i])
{
dfs(i,cur);
subsz[cur]+=subsz[i];
}
}
}
int getcentroid(int cur,int prev,int sz)
{
bool isC=true;
int hc=-1;
for(auto i:tree[cur])
{
if(i!=prev && !centroidMarked[i] && subsz[i]>sz)
{
isC=false;
hc=i;
break;
}
}
if(isC && subsz[cur]>=sz)return cur;
return getcentroid(hc,cur,sz);
}
int getcentroid(int src)
{
dfs(src,-1);
int c=getcentroid(src,-1,subsz[src]/2);
centroidMarked[c]=1;
return c;
}
int build(int root)
{
int c=getcentroid(root);
for(auto i:tree[c])
{
if(!centroidMarked[i])
{
int k=build(i);
cpar[k]=c;
}
}
return c;
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
for(int i=1;i<n;i++)
{
//cout<<A[i]<<" "<<B[i]<<endl;
tree[A[i]].push_back(B[i]);
tree[B[i]].push_back(A[i]);
cost[A[i]].push_back(D[i]);
cost[B[i]].push_back(D[i]);
}
dfs1(0,-1,0);
cpar[build(0)]=-1;
for(int i=0;i<n;i++)ans[i]=inf;
for(int i=0;i<n;i++)
{
int x=1;
int cur=i;
while(cur!=-1)
{
int lca=findLCA(i,cur);
cdist[x++][i]=getDist(i,lca)+getDist(lca,cur);
cur=cpar[cur];
}
}
}
void prc(int u,bool f)
{
int x=2;
ans[u]=(f?0:inf);
int cur=cpar[u];
while(cur!=-1)
{
if(f)ans[cur]=min(ans[cur],cdist[x++][u]);
else ans[cur]=inf;
cur=cpar[cur];
}
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0;i<S;i++)prc(X[i],true);
ll res=inf;
for(int i=0;i<T;i++)
{
int x=1;
int cur=Y[i];
while(cur!=-1)
{
res=min(res,ans[cur]+cdist[x++][Y[i]]);
cur=cpar[cur];
}
}
for(int i=0;i<S;i++)prc(X[i],false);
return res;
}
