#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<ll, pi>
#define fi first
#define se second
#define getchar_unlocked getchar_nolock
ll n, m, q;
vector<pi>v[500005];
vector<ll> ct[500005];
ll dep[500005], par[20][500005], sz[500005], vis[500005];
ll dist[500005][20];
ll mn[500005];
ll di[5000005];
void dfs(int x, int p, int d){
sz[x] = 1;
for(auto [i, j] : v[x]){
if(i == p || vis[i])continue;
dfs(i, x, d + 1);
sz[x] += sz[i];
}
}
int rt, lim;
int cent(int x, int p){
for(auto [i, j] : v[x]){
if(i == p || vis[i])continue;
if(sz[i] * 2 > lim)return cent(i, x);
}
return x;
}
int lvl = 1;
void dfs2(int x, int p, ll cur){
dist[x][lvl] = cur;
for(auto [i, j] : v[x]){
if(i == p || vis[i])continue;
dfs2(i, x, cur + j);
}
}
void proc(int x, int p){
par[0][x] = p;
dep[x] = (p == -1 ? 0 : dep[p]) + 1;
for(auto i : ct[x])if(i != p)proc(i, x);
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++)A[i]++, B[i]++, v[A[i]].push_back({B[i], D[i]}), v[B[i]].push_back({A[i], D[i]});
dfs(1, -1, 1);
lim = N;
int x = cent(1, -1);
rt = x;
queue<pi>qu;
qu.push({x, 1});
//cerr << rt << '\n';
vis[x] = 1;
while(!qu.empty()){
x = qu.front().fi;
int y = qu.front().se; qu.pop();
vis[x] = 1;
lvl = y;
dfs2(x, -1, 0);
for(auto [i, j] : v[x]){
if(vis[i])continue;
dfs(i, x, 1);
lim = sz[i];
int lmao = cent(i, x);
ct[x].push_back(lmao);
ct[lmao].push_back(x);
//cerr << "ADDING EDGE " << x << " " << lmao << "\n";
qu.push({lmao, y + 1});
}
}
assert(lvl <= 20);
proc(rt, -1);
for(int i=1;i<=N;i++)mn[i] = 1e18;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int>tmp;
for(int i=0;i<S;i++)X[i]++;
for(int i=0;i<T;i++)Y[i]++;
for(int i=0;i<T;i++){
int ori = Y[i];
mn[ori] = 0;
while(ori != -1){
mn[ori] = min(mn[ori], dist[Y[i]][dep[ori]]);
tmp.push_back(ori);
ori = par[0][ori];
}
}
ll ans = 1e18;
for(int i=0;i<S;i++){
ll ans2 = mn[X[i]], ori = X[i];
while(ori != -1){
ans2 = min(ans2, mn[ori] + dist[X[i]][dep[ori]]);
ori = par[0][ori];
}
ans = min(ans, ans2);
}
for(auto i : tmp)mn[i] = 1e18;
return ans;
}
