#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> II;
const int N = 5e5 + 3;
const int logN = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
int n, child[N], a[N], b[N], d[N], q, f[N][logN], depth[N], x[N], y[N], s, t;
bool ers[N];
vector<II> g[N], par[N];
ll dist[N], root_dis[N];
void Dfs(int u = 1, int p = 0, int di = 0){
depth[u] = depth[p] + 1;
root_dis[u] = root_dis[p] + di;
f[u][0] = p;
for(int i = 1; i < logN; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
for(auto x : g[u]){
int v = x.second, uv = x.first;
if(v == p) continue;
Dfs(v, u, uv);
}
}
int lca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int i = logN - 1; i >= 0; i --){
if(depth[f[u][i]] >= depth[v]) u = f[u][i];
}
if(u == v) return u;
for(int i = logN - 1; i >= 0; i --){
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
}
return f[u][0];
}
inline ll get_dist(int u, int v){
return root_dis[u] + root_dis[v] - 2 * root_dis[lca(u, v)];
}
int dfs(int u, int p = 0){
child[u] = 1;
for(auto x : g[u]){
int v = x.second;
if(v != p && !ers[v]) child[u] += dfs(v, u);
}
return child[u];
}
int get_centroid(int u, int sz, int p = 0){
for(auto x : g[u]){
int v = x.second;
if(!ers[v] && v != p && child[v] * 2 > sz) return get_centroid(v, sz, u);
}
return u;
}
void centroid(int u = 1, int p = 0){
int cen = get_centroid(u, dfs(u));
for(auto x : par[p]) par[cen].push_back(II(x.first, get_dist(cen, x.first)));
par[cen].push_back(II(cen, 0));
ers[cen] = true;
for(auto x : g[cen]){
int v = x.second;
if(!ers[v]) centroid(v, cen);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 1; i <= n; i ++) dist[i] = INF, g[i].clear();
for(int i = 0; i <= n - 2; i ++){
A[i] ++;
B[i] ++;
g[A[i]].push_back(II(D[i], B[i]));
g[B[i]].push_back(II(D[i], A[i]));
}
Dfs();
centroid();
}
ll Query(int S, int X[], int T, int Y[]){
for(int i = 0; i < S; i ++){
X[i] ++;
for(auto x : par[X[i]]) dist[x.first] = min(dist[x.first], x.second);
}
ll ans = INF;
for(int i = 0; i < T; i ++){
Y[i] ++;
for(auto x : par[Y[i]]) ans = min(ans, dist[x.first] + x.second);
}
for(int i = 0; i < S; i ++){
for(auto x : par[X[i]]) dist[x.first] = INF;
}
return ans;
}
