#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct HLD{
int n;
vector<vector<pair<ll, int>>> v;
vector<int> depth, sz, p, top, id;
vector<ll> sm;
int cnt = 0;
HLD(int _n){
n = _n;
v.assign(n, {});
}
void pre_dfs(int nd, int ss, int d){
for(auto [x, w]: v[nd]) if(x != ss) pre_dfs(x, nd, d+1);
for(auto [x, w]: v[nd]) if(x != ss) sz[nd]+=sz[x];
depth[nd] = d;
p[nd] = ss;
}
void dfs(int nd, int ss, ll W, int tp){
top[nd] = tp;
id[nd] = cnt;
sm[id[nd]] = W;
cnt++;
int mx = 0, in = -1, inw = -1;
for(auto [x, w]: v[nd]) if(x != ss && sz[x] > mx) mx = sz[x], in = x, inw = w;
if(in != -1) dfs(in, nd, inw, tp);
for(auto [x, w]: v[nd]) if(x != ss && x != in) dfs(x, nd, w, x);
}
void init(){
depth.assign(n, 0);
sz.assign(n, 1);
p.assign(n, -1);
pre_dfs(0, -1, 0);
top.assign(n, -1);
id.assign(n, -1);
sm.assign(n, 0);
dfs(0, -1, 0, 0);
for(int i = 1; i < n; i++) sm[i]+=sm[i-1];
}
ll sum(int l, int r){
if(l > r) return 0;
return sm[r]-(l==0?0:sm[l-1]);
}
ll query(vector<pair<int, int>> sth){
ll ans = 1e18;
priority_queue<tuple<int, int, int, int, ll>> pq;
for(auto [nd, t]: sth) pq.push({depth[top[nd]], top[nd], nd, t, 0});
while(!pq.empty()){
int tp = get<1>(pq.top());
cerr << tp << " -----\n";
vector<tuple<int, int, ll>> cur;
while(!pq.empty() && get<1>(pq.top()) == tp){
cur.pb({get<2>(pq.top()), get<3>(pq.top()), get<4>(pq.top())});
pq.pop();
}
sort(cur.begin(), cur.end(), [&](tuple<int, int, ll> a, tuple<int, int, ll> b){
return depth[get<0>(a)] < depth[get<0>(b)];
});
int tn[2] = {-1,-1};
ll tc[2] = {ll(1e18), ll(1e18)};
for(int i = int(cur.size())-1; i >= 0; i--){
auto [nd, t, c] = cur[i];
if(tn[t] == -1 || c < tc[t]+sum(id[nd]+1, id[tn[t]]))
tn[t] = nd, tc[t] = c;
if(tn[1-t] != -1)
ans = min(ans, c+tc[1-t]+sum(id[nd]+1, id[tn[1-t]]));
}
tc[0] = 1e18, tc[1] = 1e18;
for(auto [nd, t, c]: cur){
tc[t] = min(tc[t], sum(id[tp], id[nd])+c);
}
if(!pq.empty()){
for(int i = 0; i < 2; i++)
if(tn[i] != -1)
pq.push({depth[top[p[tp]]], top[p[tp]], p[tp], i, tc[i]});
}
}
return ans;
}
};
HLD hld(0);
void Init(int N, int A[], int B[], int D[]){
hld = HLD(N);
for(int i = 0; i < N-1; i++){
hld.v[A[i]].pb({B[i], D[i]});
hld.v[B[i]].pb({A[i], D[i]});
}
hld.init();
}
ll Query(int S, int X[], int T, int Y[]){
vector<pair<int, int>> sth;
for(int i = 0; i < S; i++) sth.pb({X[i], 0});
for(int i = 0; i < T; i++) sth.pb({Y[i], 1});
return hld.query(sth);
}
