#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define Sz(x) int((x).size())
//#define All(x) (x).begin(), (x).end()
//#define wtf(x) cout<<#x <<" : " <<x <<endl
const ll inf = 1e18, maxn = 1e6 + 10, Log = 25;
int n, par[maxn][Log], st[maxn], fn[maxn], h[maxn], cnt[maxn], tim;
ll d[maxn], dp[maxn][2], ans;
vector<pair<int, int> > G[maxn], child[maxn];
bool cmp(int i, int j) {
return st[i] < st[j];
}
void dfs(int x, int p = 0) {
st[x] = tim++;
par[x][0] = p;
for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];
for(auto i : G[x]) {
if(i.first == p) continue;
h[i.first] = h[x] + 1, d[i.first] = d[x] + i.second;
dfs(i.first, x);
}
fn[x] = tim++;
}
int get_par(int x, int y) {
for(int i = 0; i < Log; i++) {
if((y >> i) & 1) x = par[x][i];
}
return x;
}
int lca(int x, int y) {
if(h[x] > h[y]) swap(x, y);
y = get_par(y, h[y] - h[x]);
if(x == y) return x;
for(int i = Log - 1; i >= 0; i--) {
if(par[x][i] != par[y][i]) {
x = par[x][i], y = par[y][i];
}
}
return par[x][0];
}
void main_dfs(int x) {
dp[x][0] = dp[x][1] = inf;
if(cnt[x] == 0) dp[x][0] = 0;
if(cnt[x] == 1) dp[x][1] = 0;
for(auto i : child[x]) {
main_dfs(i.first);
dp[x][0] = min(dp[x][0], dp[i.first][0] + i.second);
dp[x][1] = min(dp[x][1], dp[i.first][1] + i.second);
}
ans = min(ans, dp[x][0] + dp[x][1]);
}
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]});
}
dfs(0);
for(int i = 0; i < n; i++) cnt[i] = -1;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vc;
for(int i = 0; i < S; i++) vc.push_back(X[i]), cnt[X[i]] = 0;
for(int i = 0; i < T; i++) vc.push_back(Y[i]), cnt[Y[i]] = 1;
sort(vc.begin(), vc.end(), cmp);
int sz = vc.size();
for(int i = 0; i < sz - 1; i++) {
vc.push_back(lca(vc[i], vc[i + 1]));
}
sort(vc.begin(), vc.end(), cmp);
vc.erase(unique(vc.begin(), vc.end()), vc.end());
stack<int> st;
st.push(vc[0]);
for(int i = 1; i < vc.size(); i++) {
int v = vc[i];
while(fn[st.top()] < fn[v]) st.pop();
child[st.top()].push_back({v, d[v] - d[st.top()]});
st.push(v);
}
ans = inf;
main_dfs(vc[0]);
for(auto i : vc) {
child[i].clear();
cnt[i] = -1;
}
return ans;
}
