#include "factories.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5e5 + 5;
const int logn = log2(maxn) + 1;
typedef pair<int,int> ii;
typedef long long ll;
int big[maxn] , vis[maxn] , n , sub[maxn];
ll dep[maxn] , cen[maxn];
vector<int> v[maxn];
vector<ii> adj[maxn];
vector<ll> predis[maxn];
void DFS(int u , int v){
sub[u] = 1;
big[u] = -1;
for(auto& c : adj[u]){
if(c.first != v && vis[c.first] == 0){
DFS(c.first , u);
sub[u] += sub[c.first];
if(big[u] == -1 || sub[big[u]] < sub[c.first])big[u] = c.first;
}
}
}
int FindRoot(int u){
DFS(u , -1);
int total = sub[u];
while(big[u] != -1 && sub[big[u]] * 2 >= total)u = big[u];
return u;
}
void Decompose(int u){
u = FindRoot(u);
vis[u] = 1;
function<void(int,int,ll dep)> DFS = [&](int uu , int v , ll dep){
::v[uu].pb(u);
predis[uu].pb(dep);
for(ii c : adj[uu]){
if(c.first != v && vis[c.first] == 0){
DFS(c.first , uu , dep + c.second);
}
}
};
DFS(u , -1 , 0);
for(auto& c : adj[u]){
if(vis[c.first] == 0){
Decompose(c.first);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0 ; i < n - 1 ; ++i){
adj[A[i]].pb(mp(B[i] , D[i]));
adj[B[i]].pb(mp(A[i] , D[i]));
}
Decompose(0);
for(int i = 0 ; i < n ; ++i)cen[i] = 1e18;
}
long long Query(int S, int X[], int T, int Y[]) {
ll total = 1e18;
for(int i = 0 ; i < S ; ++i){
for(int j = (int)v[X[i]].size() -1; j >= 0 ; --j){
cen[v[X[i]][j]] = min(cen[v[X[i]][j]] , predis[X[i]][j]);
}
}
for(int i = 0 ; i < T ; ++i){
ll res = 1e18;
for(int j = (int)v[Y[i]].size() -1; j >= 0 ; --j){
res = min(res , predis[Y[i]][j] + cen[v[Y[i]][j]]);
}
total = min(total , res);
}
for(int i = 0 ; i < S ; ++i){
for(int c : v[X[i]]){
cen[c] = 1e18;
}
}
return total;
}
