#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int M = 1e5 + 2;
int mod = 1000000007;
vector<array<int, 2>> g[N];
int sz[N];
bool was[N];
ll mn[N];
void Dfs(int s, int e) {
sz[s] = 1;
for (auto u : g[s]) {
if (u[0] == e || was[u[0]]) continue;
Dfs(u[0], s);
sz[s] += sz[u[0]];
}
}
int Find(int s, int e, int n) {
for (auto u : g[s]) {
if (u[0] == e || was[u[0]]) continue;
if (2 * sz[u[0]] > n) return Find(u[0], s, n);
}
return s;
}
int FindCentroid(int node) {
Dfs(node, -1);
return Find(node, -1, sz[node]);
}
vector<array<ll, 2>> p[N];
void Solve(int s, int e, int r, ll d) {
p[s].push_back({r, d});
for (auto u : g[s]) {
if (was[u[0]] || u[0] == e) continue;
Solve(u[0], s, r, d + u[1]);
}
}
void Decompose(int s) {
s = FindCentroid(s);
was[s] = 1;
Solve(s, -1, s, 0);
for (auto u : g[s]) {
if (!was[u[0]]) Decompose(u[0]);
}
}
void Init(int n, int *a, int *b, int* d) {
for (int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], d[i]});
g[b[i]].push_back({a[i], d[i]});
}
Decompose(0);
for (int i = 0; i < n; i++) mn[i] = 1e18;
}
ll Query(int a, int *x, int b, int *y) {
vector<int> ch;
for (int j = 0; j < a; j++) {
for (auto d : p[x[j]]) {
smin(mn[d[0]], d[1]);
ch.push_back(d[0]);
}
}
ll ans = 1e18;
for (int j = 0; j < b; j++) {
for (auto d : p[y[j]]) {
smin(ans, mn[d[0]] + d[1]);
}
}
for (int u : ch) mn[u] = 1e18;
return ans;
}
