// ~~ icebear ~~
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 5e5 + 5;
int n;
vector<ii> G[N];
int par[N], sz[N], minHigh[20][N << 1], pos[N], tour[N << 1], timer = 0, h[N];
ll f[N];
void prepare(int u, int par) {
pos[u] = ++timer;
tour[timer] = u;
for(ii v : G[u]) if (v.fi != par) {
h[v.fi] = h[u] + 1;
f[v.fi] = f[u] + v.se;
prepare(v.fi, u);
tour[++timer] = u;
}
}
#define MIN_HIGH(x, y) (h[x] < h[y] ? x : y)
int LCA(int u, int v) {
int l = pos[u], r = pos[v];
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
return MIN_HIGH(minHigh[l][k], minHigh[r - MASK(k) + 1][k]);
}
ll dist(int u, int v) {
int p = LCA(u, v);
return f[u] + f[v] - 2 * f[p];
}
bool isCentroid[N];
int calc_sz(int u, int par) {
sz[u] = 1;
for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi])
sz[u] += calc_sz(v.fi, u);
return sz[u];
}
int findCentroid(int u, int par, const int &S) {
for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi] && sz[v.fi] * 2 > S)
return findCentroid(v.fi, u, S);
return u;
}
void buildCentroid(int u, int pre) {
int centroid = findCentroid(u, -1, calc_sz(u, -1));
isCentroid[centroid] = true;
par[centroid] = pre;
for(ii v : G[centroid]) if (!isCentroid[v.fi])
buildCentroid(v.fi, centroid);
}
ll minDist[N];
void Init(int N, vector<int> A, vector<int> B, vector<int> D) {
n = N;
REP(i, N - 1) {
G[A[i]].pb(mp(B[i], D[i]));
G[B[i]].pb(mp(A[i], D[i]));
}
prepare(0, -1);
FOR(i, 1, timer) minHigh[i][0] = tour[i];
FOR(j, 1, 19) FOR(i, 1, timer - MASK(j) + 1)
minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + MASK(j - 1)][j - 1]);
buildCentroid(0, -1);
memset(minDist, 0x3f, sizeof minDist);
}
void update(int u) {
int node = u;
while(node >= 0) {
minimize(minDist[node], dist(u, node));
node = par[node];
}
}
void set_off(int u) {
int node = u;
while(node > 0) {
minDist[node] = INF;
node = par[node];
}
}
ll getMin(int u) {
ll ans = INF;
int node = u;
while(node > 0) {
minimize(ans, minDist[node] + dist(u, node));
node = par[node];
}
return ans;
}
ll Query(int S, vector<int> X, int T, vector<int> Y) {
for(int &u : X) update(u);
ll ans = INF;
for(int &v : Y) minimize(ans, getMin(v));
for(int &u : X) set_off(u);
return ans;
}
// int main() {
// Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
// cout << Query(2, {0, 6}, 2, {3, 4}) << ' ' << Query(3, {0, 1, 3}, 2, {4, 6}) << ' ' << Query(1, {2}, 1, {5});
// return 0;
// }
