#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#pragma GCC_optimize("O3")
int n, dep[500001], par[500001][20];
ll sum[500001];
vector <pair <int, ll> > v[500001];
void dfs(int node, int pnode, int d, ll s){
par[node][0] = pnode;
dep[node] = d;
sum[node] = s;
for(auto &i : v[node])
if(i.first != pnode)
dfs(i.first, node, d + 1, s + i.second);
}
void build(){
dfs(0, -1, 0, 0);
int cur = 1;
while((1 << cur) <= n){
for(int i = 0 ; i < n ; i++){
if(par[i][cur - 1] == -1) par[i][cur] = -1;
else par[i][cur] = par[par[i][cur - 1]][cur - 1];
}
cur++;
}
}
int lift(int node, int dist){
for(int i = 19 ; i >= 0 ; i--)
if((1 << i) & dist)
node = par[node][i];
return node;
}
int LCA(int a, int b){
if(dep[a] > dep[b])
swap(a, b);
b = lift(b, dep[b] - dep[a]);
if(a == b) return a;
for(int i = 19 ; i >= 0 ; i--){
if(par[a][i] != par[b][i]){
a = par[a][i];
b = par[b][i];
}
}
return par[a][0];
}
ll dist(int a, int b){
int lca = LCA(a, b);
return sum[a] + sum[b] - 2 * sum[lca];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0 ; i < N - 1 ; i++){
v[A[i]].push_back(make_pair(B[i], D[i]));
v[B[i]].push_back(make_pair(A[i], D[i]));
}
build();
}
long long Query(int S, int X[], int T, int Y[]) {
ll ret = 1e18;
for(int i = 0 ; i < S ; i++)
for(int j = 0 ; j < T ; j++)
ret = min(ret, dist(X[i], Y[j]));
return ret;
}
