#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int> par[500005][30];
vector<pair<int,int>> adj[500005];
int depth[500005];
void dfs(int cur,int d){
depth[cur]=d;
for (auto [j,i]:adj[cur]){
if (par[cur][0].second==i) continue;
par[i][0]={j,cur};
dfs(i,d+1);
}
}
int dis(int x,int y){
int ret=0;
if (depth[x]<depth[y]) swap(x,y);
for (int k=19;k>=0;k--){
if (depth[par[x][k].second]>=depth[y]){
ret+=par[x][k].first;
x=par[x][k].second;
}
}
if (x==y) return ret;
for (int k=19;k>=0;k--){
if (par[x][k].second!=par[y][k].second){
ret+=par[x][k].first;
x=par[x][k].second;
ret+=par[y][k].first;
y=par[y][k].second;
}
}
return ret+par[x][0].first+par[y][0].first;
}
void Init(signed N, signed A[], signed B[], signed D[]) {
for (int i=0;i<N-1;i++){
adj[A[i]+1].push_back({D[i],B[i]+1});
adj[B[i]+1].push_back({D[i],A[i]+1});
}
dfs(1,1);
for (int k=1;k<20;k++) for (int i=1;i<=N;i++) par[i][k]={par[i][k-1].first+par[par[i][k-1].second][k-1].first,par[par[i][k-1].second][k-1].second};
}
int Query(signed S, signed X[], signed T, signed Y[]) {
int ret=1e18;
for (int i=0;i<S;i++){
for (int j=0;j<T;j++){
ret=min(ret,dis(X[i]+1,Y[j]+1));
}
}
return ret;
}
