#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const long long N = 5e5 + 5, INF = 1e18 + 5;
long long n, cnt[N], mina[N], ans;
bool blocked[N];
struct Edge{
long long b, w;
};
vector<Edge> tree[N];
vector<Edge> parent[N];
void subtreecnt(int v, int p){
cnt[v] = 1;
for(auto e : tree[v]){
if(e.b != p && !blocked[e.b]){
subtreecnt(e.b, v);
cnt[v] += cnt[e.b];
}
}
}
int findcentroid(int v, int p, int root){
for(auto e : tree[v]){
if(e.b != p && !blocked[e.b] && cnt[e.b] > cnt[root] / 2){
return findcentroid(e.b, v, root);
}
}
return v;
}
void findpaths(int v, int p, int centroid, long long curw){
parent[v].push_back({centroid, curw});
for(auto e : tree[v]){
if(e.b != p && !blocked[e.b]) findpaths(e.b, v, centroid, curw + e.w);
}
}
void decomp(int v){
subtreecnt(v, -1);
int centroid = findcentroid(v, -1, v);
findpaths(centroid, -1, centroid, 0);
blocked[centroid] = true;
for(auto e : tree[centroid]) if(!blocked[e.b]) decomp(e.b);
}
void Init(int n, int a[], int b[], int d[]){
for(int i = 0; i < n - 1; i++){
tree[a[i]].push_back({b[i], d[i]});
tree[b[i]].push_back({a[i], d[i]});
}
decomp(0);
for(int i = 0; i < n; i++) reverse(parent[i].begin(), parent[i].end());
fill(mina, mina + N, INF);
}
long long Query(int s, int x[], int t, int y[]){
ans = INF;
for(int i = 0; i < s; i++){
for(auto e : parent[x[i]]){
mina[e.b] = min(mina[e.b], e.w);
}
}
for(int i = 0; i < t; i++){
for(auto e : parent[y[i]]){
ans = min(ans, mina[e.b] + e.w);
}
}
for(int i = 0; i < s; i++){
for(auto e : parent[x[i]]){
mina[e.b] = INF;
}
}
return ans;
}
