#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500000 + 5;
const int LOG = 20;
const long long INF = (long long)4e18;
int n;
vector<pair<int,int>> g[MAXN];
vector<pair<int,long long>> vt[MAXN];
int tin[MAXN], tout[MAXN], timer_;
int depth_[MAXN];
int up[MAXN][LOG];
long long dist_root[MAXN];
int color[MAXN];
long long bestX[MAXN], bestY[MAXN];
bool is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int lca(int u, int v){
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(int i = LOG - 1; i >= 0; i--){
if(!is_ancestor(up[u][i], v)){
u = up[u][i];
}
}
return up[u][0];
}
long long dist(int u, int v){
int w = lca(u, v);
return dist_root[u] + dist_root[v] - 2LL * dist_root[w];
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < n - 1; i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
vector<int> it(n, 0), par(n, -1);
stack<int> st;
par[0] = 0;
up[0][0] = 0;
for(int j = 1; j < LOG; j++) up[0][j] = 0;
tin[0] = timer_++;
st.push(0);
while(!st.empty()){
int u = st.top();
if(it[u] == (int)g[u].size()){
tout[u] = timer_;
st.pop();
continue;
}
auto [v, w] = g[u][it[u]++];
if(v == par[u]) continue;
par[v] = u;
depth_[v] = depth_[u] + 1;
dist_root[v] = dist_root[u] + w;
up[v][0] = u;
for(int j = 1; j < LOG; j++){
up[v][j] = up[up[v][j - 1]][j - 1];
}
tin[v] = timer_++;
st.push(v);
}
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> nodes;
nodes.reserve(2 * (S + T));
vector<int> marked;
marked.reserve(S + T);
for(int i = 0; i < S; i++){
color[X[i]] = 1;
nodes.push_back(X[i]);
marked.push_back(X[i]);
}
for(int i = 0; i < T; i++){
color[Y[i]] = 2;
nodes.push_back(Y[i]);
marked.push_back(Y[i]);
}
sort(nodes.begin(), nodes.end(), [&](int a, int b){
return tin[a] < tin[b];
});
int m = nodes.size();
for(int i = 0; i + 1 < m; i++){
nodes.push_back(lca(nodes[i], nodes[i + 1]));
}
sort(nodes.begin(), nodes.end(), [&](int a, int b){
return tin[a] < tin[b];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
for(int u : nodes){
vt[u].clear();
bestX[u] = INF;
bestY[u] = INF;
}
vector<int> stk;
for(int u : nodes){
if(stk.empty()){
stk.push_back(u);
continue;
}
while(!is_ancestor(stk.back(), u)){
stk.pop_back();
}
int p = stk.back();
vt[p].push_back({u, dist_root[u] - dist_root[p]});
stk.push_back(u);
}
for(int u : nodes){
if(color[u] == 1) bestX[u] = 0;
if(color[u] == 2) bestY[u] = 0;
}
long long ans = INF;
for(int i = (int)nodes.size() - 1; i >= 0; i--){
int u = nodes[i];
for(auto [v, w] : vt[u]){
if(bestX[u] < INF / 2 && bestY[v] < INF / 2){
ans = min(ans, bestX[u] + bestY[v] + w);
}
if(bestY[u] < INF / 2 && bestX[v] < INF / 2){
ans = min(ans, bestY[u] + bestX[v] + w);
}
bestX[u] = min(bestX[u], bestX[v] + w);
bestY[u] = min(bestY[u], bestY[v] + w);
}
}
for(int u : marked){
color[u] = 0;
}
return ans;
}
