#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 3e5 + 10;
const ll INF = 1e18;
// Author : T_Danh - Tri An High School
struct Anc {
int ancestor;
ll dist;
};
int n;
ll dist[N + 1];
ll dist_to_anc[N + 1][2];
vector<pii> adj[N + 1];
vector<Anc> ancestors[N + 1];
vector<int> vis_anc;
int sz[N + 1];
bool removed[N + 1];
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto& to : adj[u]) {
if (to.fi != p && !removed[to.fi]) {
dfs_sz(to.fi, u);
sz[u] += sz[to.fi];
}
}
}
int find_centroid(int u, int p, int total) {
for (auto& to : adj[u]) {
if (to.fi != p && !removed[to.fi] && sz[to.fi] > total / 2)
return find_centroid(to.fi, u, total);
}
return u;
}
void reset_dist(int u, int p, int centroid) {
ancestors[u].eb(centroid , dist[u]);
dist[u] = INF;
for(auto& to : adj[u]){
if(!removed[to.fi] && to.fi != p){
reset_dist(to.fi , u , centroid);
}
}
}
void build(int cur) {
dfs_sz(cur, -1);
int centroid = find_centroid(cur, -1, sz[cur]);
removed[centroid] = true;
priority_queue<pair<ll,int> , vector<pair<ll,int>> , greater<pair<ll,int>>> q;
q.push({0, centroid});
dist[centroid] = 0;
while(!q.empty()){
ll d = q.top().fi ;int u = q.top().se; q.pop();
if(dist[u] != d) continue;
for(auto& to : adj[u]) if(!removed[to.fi]){
ll nd = d + to.se;
int v = to.fi;
if(nd < dist[v]){
q.push({dist[v] = nd, v});
}
}
}
reset_dist(centroid , centroid , centroid);
for (auto& to : adj[centroid]) {
if (!removed[to.fi]) build(to.fi);
}
}
void add(int u , int type){
for(Anc& anc : ancestors[u]){
dist_to_anc[anc.ancestor][type] = min(dist_to_anc[anc.ancestor][type] , anc.dist);
vis_anc.eb(anc.ancestor);
}
}
void Init(int N , int A[] , int B[] , int D[]){
n = N;
FOR(i,0,n-2){
adj[A[i]].eb(B[i] , D[i]);
adj[B[i]].eb(A[i] , D[i]);
}
build(1);
}
ll query(int S , int X[] , int T , int Y[]) {
ll ans = INF;
FOR(i,0,S-2){
add(X[i] , 0);
}
FOR(i,0,T - 2){
add(Y[i] , 1);
}
for(int i : vis_anc){
ans = min(ans , dist_to_anc[i][0] + dist_to_anc[i][1]);
dist_to_anc[i][0] = dist_to_anc[i][1] = INF;
}
vis_anc.clear();
return ans;
}
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// #define NAME "newbarn"
// if (fopen(NAME ".in", "r")) {
// freopen(NAME ".in", "r", stdin);
// freopen(NAME ".out", "w", stdout);
// }
// return 0;
// }
