#include <bits/stdc++.h>
//#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll inf = 1e14 + 2;
vector<ll> minn(N);
vector<int> sz(N), used(N, 0);
vector<vector<pair<int, ll>>> adj(N), ancestors(N);
int n;
void find_sz(int node, int parent) {
sz[node] = 1;
for (auto child : adj[node]) {
if (child.first == parent || used[child.first]) continue;
find_sz(child.first, node);
sz[node] += sz[child.first];
}
}
void update(int node, int parent, int c, ll d) {
ancestors[node].push_back(make_pair(c, d));
for (auto child : adj[node]) {
if (child.first == parent || used[child.first]) continue;
update(child.first, node, c, d + child.second);
}
}
void find_cent(int node, int parent, int size) {
for (auto child : adj[node]) {
if (child.first == parent || used[child.first]) continue;
if (sz[child.first] * 2 > size) {
find_cent(child.first, node, size);
return;
}
}
update(node, -1, node, 0);
used[node] = 1;
find_sz(node, -1);
for (auto child :adj[node]) {
if (used[child.first]) continue;
find_cent(child.first, node, sz[child.first]);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; i++) {
adj[A[i]].push_back(make_pair(B[i], D[i]));
adj[B[i]].push_back(make_pair(A[i], D[i]));
}
find_sz(0, -1);
find_cent(0, -1, N);
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0;i<T;i++){
for(pair<int,long long> y:ancestors[Y[i]]){
minn[y.fi]=inf;
}
}
for(int i=0;i<S;i++){
for(pair<int,ll> y:ancestors[X[i]]){
minn[y.fi]=min(minn[y.fi],y.se);
}
}
ll ans=inf;
for(int i=0;i<T;i++){
for(pair<int,ll> y:ancestors[Y[i]]){
ans=min(ans,minn[y.fi]+y.se);
}
}
return ans;
}
