#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e14;
const int N = 5e5+50;
int timer = 1;
vector<pii> edges[N];
int up[N][20],d[N],tin[N],tout[N],c[N],red[N],blue[N];
void dfs(int node,int p,int dep = 0) {
tin[node] = timer++;
d[node] = dep;
up[node][0] = p;
for (auto it : edges[node]) {
if (it.ff == p) continue;
dfs(it.ff,node,dep+it.ss);
}
tout[node] = timer-1;
}
bool anc(int a,int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a,int b) {
if (anc(a,b)) return a;
if (anc(b,a)) return b;
for (int i=19;i>=0;i--) {
if (!anc(up[a][i],b)) a = up[a][i];
}
return up[a][0];
}
vi edg[N];
int solver(int node) {
red[node] = blue[node] = inf;
if (c[node] == 1) red[node] = d[node];
if (c[node] == 2) blue[node] = d[node];
int ans = inf;
for (auto it : edg[node]) {
ans = min(ans,solver(it));
red[node] = min(red[node],red[it]);
blue[node] = min(blue[node],blue[it]);
}
//cout << node sp red[node] sp blue[node] sp d[node]<< endl;
ans = min(ans,red[node]+blue[node]-2*d[node]);
return ans;
}
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
int n = N;
for (int i=0;i<n-1;i++) {
edges[A[i]].push_back({B[i],D[i]});
edges[B[i]].push_back({A[i],D[i]});
}
dfs(0,0);
for (int i=1;i<20;i++) {
for (int j=0;j<n;j++) up[j][i] = up[up[j][i-1]][i-1];
}
}
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
int s = S,t = T;
vector<int> nodes;
for (int i=0;i<s;i++) {
c[X[i]] = 1;
nodes.push_back(X[i]);
}
for (int i=0;i<t;i++) {
c[Y[i]] = 2;
nodes.push_back(Y[i]);
}
sort(all(nodes),[&](int n1,int n2) {
return tin[n1] < tin[n2];
});
for (int i=0;i<s+t;i++) {
nodes.push_back(lca(nodes[i],nodes[(i+1)%nodes.size()]));
}
sort(all(nodes),[&](int n1,int n2) {
return tin[n1] < tin[n2];
});
nodes.erase(unique(all(nodes)),nodes.end());
stack<int> st;
st.push(nodes[0]);
for (int i=1;i<nodes.size();i++) {
while (!anc(st.top(),nodes[i])) {
st.pop();
}
edg[st.top()].push_back(nodes[i]);
st.push(nodes[i]);
}
int ans = solver(nodes[0]);
for (auto it : nodes) edg[it].clear(),c[it] = 0;
return ans;
}
