#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
const int N=5e5+1, LG=20;
int n, nvt, tdfs, st_cnt, tin[N], tout[N], dep[N], pos_st[N], dis[N], color[N];
pair<int, int> st[N*2][LG];
vector<pair<int, int>> g[N], vt[N];
void pre_dfs(int u, int p){
tin[u]=++tdfs;
st[++st_cnt][0]={dep[u], u};
pos_st[u]=st_cnt;
for (auto& e:g[u]){
int v=e.first, w=e.second;
if (v==p) continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+w;
pre_dfs(v, u);
st[++st_cnt][0]={dep[u], u};
}
tout[u]=tdfs;
}
void build_st(){
for (int k=1; k<LG; ++k){
for (int l=1; l+(1<<k)-1<=st_cnt; ++l){
st[l][k]=min(st[l][k-1], st[l+(1<<(k-1))][k-1]);
}
}
}
int lca(int u, int v){
u=pos_st[u], v=pos_st[v];
if (u>v) swap(u, v);
int lg=__lg(v-u+1);
return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}
bool is_ancestor(int u, int v){
return tin[u]<=tin[v] && tin[v]<=tout[u];
}
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
memset(color, -1, sizeof color);
n=N;
for (int i=0; i<n-1; ++i){
++A[i]; ++B[i];
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
pre_dfs(1, 0);
build_st();
}
pair<int, int> dfs(int u, int p, int& ans){
pair<int, int> wtf={1e18, 1e18};
if (color[u]==0) wtf.first=0;
else if (color[u]==1) wtf.second=0;
for (auto& e:vt[u]){
int v=e.first, w=e.second;
if (v==p) continue;
auto lmao=dfs(v, u, ans);
wtf.first=min(wtf.first, lmao.first+w);
wtf.second=min(wtf.second, lmao.second+w);
}
ans=min(ans, wtf.first+wtf.second);
return wtf;
}
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
vector<int> vtn;
for (int i=0; i<S; ++i) ++X[i], color[X[i]]=0;
for (int i=0; i<T; ++i) ++Y[i], color[Y[i]]=1;
for (int i=0; i<S; ++i) vtn.push_back(X[i]);
for (int i=0; i<T; ++i) vtn.push_back(Y[i]);
sort(all(vtn), [&](int u, int v) -> bool {
return tin[u]<tin[v];
});
for (int i=0; i<S+T-1; ++i) vtn.push_back(lca(vtn[i], vtn[i+1]));
sort(all(vtn), [&](int u, int v) -> bool {
return tin[u]<tin[v];
});
vtn.resize(unique(all(vtn))-vtn.begin());
for (int i:vtn) vt[i].clear();
stack<int> st;
for (int i:vtn){
while (st.size() && !is_ancestor(st.top(), i)) st.pop();
if (st.empty()) st.push(i);
else{
vt[st.top()].emplace_back(i, dis[i]-dis[st.top()]);
vt[i].emplace_back(st.top(), dis[i]-dis[st.top()]);
st.push(i);
}
}
int ans=1e18;
dfs(vtn[0], 0, ans);
for (int i=0; i<S; ++i) color[X[i]]=-1;
for (int i=0; i<T; ++i) color[Y[i]]=-1;
return ans;
}
