#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 h[maxn] , P[maxn][logn];
int big[maxn] , vis[maxn] , n , sub[maxn];
ll dep[maxn] , cen[maxn];
vector<int> v[maxn] , now;
vector<ii> adj[maxn];
void DFS(int u , int v){
now.pb(u);
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){
now.clear();
DFS(u , -1);
int total = sub[u];
while(big[u] != -1 && sub[big[u]] * 2 > total)u = big[u];
// cout << big[u] << endl;
// cout << u << endl;
// for(int c : now)cout << c << " ";
// cout << endl;
return u;
}
void Decompose(int u){
u = FindRoot(u);
for(int & c : now)v[c].pb(u);
vis[u] = 1;
for(auto& c : adj[u]){
// cout << u << " " << c.first << endl;
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]));
}
function<void(int,int)> DFS = [&](int u , int v){
for(auto & c : adj[u]){
if(c.first != v){
h[c.first] = h[u] + 1;
dep[c.first] = dep[u] + c.second;
P[c.first][0] = u;
for(int i = 1 ; i < logn ; ++i){
P[c.first][i] = P[P[c.first][i - 1]][i - 1];
}
DFS(c.first , u);
}
}
};
memset(P,-1,sizeof P);
DFS(0 , -1);
Decompose(0);
for(int i = 0 ; i < n ; ++i)cen[i] = 1e18;
}
int LCA(int u , int v){
if(h[u] < h[v])swap(u , v);
for(int i = 0 ; i < logn ; ++i){
if((h[u] - h[v]) & (1 << i))u = P[u][i];
}
if(u == v)return u;
for(int i = logn - 1 ; i >= 0 ; --i){
if(P[u][i] != P[v][i]){
u = P[u][i];
v = P[v][i];
}
}
return P[u][0];
}
ll dis(int u , int v){
return dep[u] + dep[v] - 2 * dep[LCA(u , v)];
}
long long Query(int S, int X[], int T, int Y[]) {
// cout << endl;
ll total = 1e18;
for(int i = 0 ; i < S ; ++i){
for(int c : v[X[i]]){
// cout << X[i] << " " << c << " " << dis(c , X[i]) << endl;
cen[c] = min(cen[c] , dis(c , X[i]));
}
}
// cout << endl;
for(int i = 0 ; i < T ; ++i){
ll res = 1e18;
for(int c : v[Y[i]]){
// cout << Y[i] << " " << c << " " << dis(c , Y[i]) << endl;
res = min(res , dis(c , Y[i]) + cen[c]);
}
total = min(total , res);
}
for(int i = 0 ; i < S ; ++i){
for(int c : v[X[i]]){
cen[c] = 1e18;
}
}
// cout << endl;
return total;
}
