#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e17;
const int MAXN=2e6+6;
const int lg=23;
ll ans;
vector<pair<int,ll> >g[MAXN];
vector<int>g1[MAXN];
int par[MAXN];
pair<int,int> dp[2*MAXN][lg];
int depth[MAXN];
ll depth1[MAXN];
int pw[2*MAXN],n;
int wherel[MAXN],wherer[MAXN];
vector<int>dfs_order;
int st[MAXN];
bool f[MAXN];
ll mind[MAXN];
void dfs1(int u,int p)
{
dfs_order.push_back(u);
for(auto v:g[u])
{
if(v.first==p)continue;
depth1[v.first]=depth1[u]+v.second;
depth[v.first]=depth[u]+1;
dfs1(v.first,u);
dfs_order.push_back(u);
}
}
void precompute()
{
int t=1,c=0;
for(int i=1;i<=MAXN;i++)
{
if(t*2<=i)
{
t*=2;c++;
}
pw[i]=c;
}
for(int i=0;i<dfs_order.size();i++)
{
dp[i][0]={depth[dfs_order[i]],dfs_order[i]};
}
for(int i=0;i<dfs_order.size();i++)
{
wherer[dfs_order[i]]=i;
}
for(int i=dfs_order.size()-1;i>=0;i--)
{
wherel[dfs_order[i]]=i;
}
for(int step=1;step<lg;step++)
{
for(int i=0;i<dfs_order.size();i++)
{
dp[i][step]=dp[i][step-1];
if(i+(1<<(step-1))<dfs_order.size())
{
dp[i][step]=min(dp[i][step],dp[i+(1<<(step-1))][step-1]);
}
}
}
}
int lca(int x,int y)
{
if(wherel[x]>wherel[y])swap(x,y);
int i1=wherel[x];
int i2=wherer[y];
int d=i2-i1+1;
int t=pw[d];
pair<int,int>ret=dp[i1][t];
ret=min(ret,dp[i2-(1<<t)+1][t]);
return ret.second;
}
ll dist(int x,int y)
{
return depth1[x]+depth1[y]-2*depth1[lca(x,y)];
}
void dfs2(int u,int p)
{
st[u]=1;
for(auto v:g[u])
{
if(v.first==p)continue;
if(f[v.first])continue;
dfs2(v.first,u);
st[u]+=st[v.first];
}
}
int find(int u,int p,int t)
{
for(auto v:g[u])
{
if(v.first==p)continue;
if(f[v.first])continue;
if(st[v.first]>t/2)return find(v.first,u,t);
}
return u;
}
void decompose(int u,int p)
{
dfs2(u,p);
int c=find(u,p,st[u]);
if(p>0)
{
g1[p].push_back(c);
}
par[c]=p;
f[c]=1;
for(auto v:g[c])
{
if(f[v.first])continue;
decompose(v.first,c);
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n-1;i++)
{
g[A[i]+1].push_back({B[i]+1,D[i]});
g[B[i]+1].push_back({A[i]+1,D[i]});
}
dfs1(1,0);
precompute();
decompose(1,-1);
for(int i=0;i<MAXN;i++)mind[i]=INF;
}
void update(int x)
{
mind[x]=0;
int y=par[x];
while(y>0)
{
mind[y]=min(mind[y],dist(x,y));
y=par[y];
}
}
void clear(int x)
{
mind[x]=INF;
int y=par[x];
while(y>0)
{
mind[y]=INF;
y=par[y];
}
}
void check(int x)
{
ans=min(ans,mind[x]);
int y=par[x];
while(y>0)
{
ans=min(ans,mind[y]+dist(x,y));
y=par[y];
}
}
long long Query(int S, int X[], int T, int Y[]) {
ans=INF;
for(int i=0;i<S;i++)
{
update(X[i]+1);
}
for(int i=0;i<T;i++)
{
check(Y[i]+1);
}
for(int i=0;i<S;i++)
{
clear(X[i]+1);
}
return ans;
}
