#include "factories.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
pair<int, ll> d[500005];
bool act[500005];
vector<pair<int, ll> > cen[500005];
vector<pair<int, ll> > adj[500005];
void dfs3(int root, int v, int p = -1, ll d = 0){
cen[v].push_back({root, d});
for(auto& x : adj[v]){
int u = x.ff;
if(act[u] || p == u)
continue;
dfs3(root, u, v, d + x.ss);
}
}
int q = 100004;
int sz[500005];
void dfs1(int v, int p = -1){
sz[v] = 1;
for(auto& x : adj[v]){
int u = x.ff;
if(act[u] || p == u)
continue;
dfs1(u, v);
sz[v] += sz[u];
}
}
int dfs2(int v, int p, int s){
for(auto& x : adj[v]){
int u = x.ff;
if(act[u] || p == u)
continue;
if(sz[u] > s)
return dfs2(u, v, s);
}
return v;
}
void decomp(int v){
dfs1(v);
v = dfs2(v, -1, sz[v] / 2);
dfs3(v, v);
act[v] = 1;
for(auto& x : adj[v]){
if(act[x.ff])
continue;
decomp(x.ff);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N; i++)
d[i] = {100005, 0};
for(int i = 0; i < N - 1; i++){
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
decomp(0);
}
long long Query(int S, int X[], int T, int Y[]) {
--q;
ll res = 0x3f3f3f3f3f3f3f3f;
for(int i = 0; i < S; i++){
for(auto& x : cen[X[i]]){
d[x.ff] = min(d[x.ff], {q, x.ss});
}
}
for(int i = 0; i < T; i++){
for(auto& x : cen[Y[i]]){
if(d[x.ff].ff == q){
res = min(res, d[x.ff].ss + x.ss);
}
}
}
return res;
}
