#include "factories.h"
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
typedef pair < int, ll > pil;
typedef pair < ll, ll > pll;
const int N = 5e5 + 500;
const int LOG = 20;
int ima[N][2], par[N][LOG], dep[N], L[N], R[N], tme, n;
ll dis[N][LOG];
vector < pii > v[N];
vector < pil > g[N];
void dfs(int x, int lst){
L[x] = tme++;
for(pii nxt : v[x]){
if(nxt.X == lst) continue;
dep[nxt.X] = dep[x] + 1;
par[nxt.X][0] = x;
dis[nxt.X][0] = nxt.Y;
dfs(nxt.X, x);
}
R[x] = tme - 1;
}
inline bool predak(int x, int y){
return L[x] <= L[y] && L[y] <= R[x];
}
void precompute(){
for(int j = 1;j < LOG;j++){
for(int i = 0;i < n;i++){
par[i][j] = par[par[i][j - 1]][j - 1];
dis[i][j] = dis[i][j - 1] + dis[par[i][j - 1]][j - 1];
}
}
}
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
if(predak(y, x)) return y;
for(int i = LOG - 1;i >= 0;i--)
if(dep[x] - dep[y] >= (1 << i))
x = par[x][i];
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];
}
bool raz(int x, int y){
return (ima[x][0] && ima[y][1]) || (ima[x][1] && ima[y][0]);
}
ll get_dis(int x, int y){
if(!predak(x, y)) return (ll)1e18;
ll ret = 0;
for(int i = LOG - 1; i >= 0;i--)
if(dep[y] - dep[x] >= (1 << i)){
ret += dis[y][i];
y = par[y][i];
}
return ret;
}
ll sol = 1e18;
pll f(int x){
if(ima[x][0] && ima[x][1]){
sol = min(sol, 0LL);
return {0, 0};
}
pll ret = {(ll)1e18 * (!ima[x][0]), (ll)1e18 * (!ima[x][1])};
for(pil nxt : g[x]){
pll nov = f(nxt.X);
nov.X += nxt.Y, nov.Y += nxt.Y;
sol = min(sol, min(nov.X + ret.Y, nov.Y + ret.X));
ret.X = min(ret.X, nov.X);
ret.Y = min(ret.Y, nov.Y);
}
return ret;
}
void Init(int nn, int a[], int b[], int d[]) {
n = nn;
for(int i = 0;i + 1 < n;i++){
v[a[i]].PB({b[i], d[i]});
v[b[i]].PB({a[i], d[i]});
}
dfs(0, 0); precompute();
}
bool cmp(int x, int y){
return L[x] < L[y];
}
ll Query(int s, int x[], int t, int y[]) {
//printf("kverij\n");
vector < int > sve;
for(int i = 0;i < s;i++){
ima[x[i]][0] = 1;
sve.PB(x[i]);
}
for(int i = 0;i < t;i++){
ima[y[i]][1] = 1;
sve.PB(y[i]);
}
sort(sve.begin(), sve.end(), cmp);
sve.erase(unique(sve.begin(), sve.end()), sve.end());
int m = (int)sve.size();
for(int i = 0;i + 1 < m;i++){
sve.PB(lca(sve[i], sve[i + 1]));
}
sort(sve.begin(), sve.end(), cmp);
sve.erase(unique(sve.begin(), sve.end()), sve.end());
m = (int)sve.size();
stack < int > S; S.push(sve[0]);
for(int i = 1;i < m;i++){
while(!predak(S.top(), sve[i]))
S.pop();
g[S.top()].PB({sve[i], get_dis(S.top(), sve[i])});
//printf("%d -- %lld --> %d\n", S.top(), g[S.top()].back().Y, sve[i]);
S.push(sve[i]);
}
sol = 1e18; f(sve[0]);
for(int i = 0;i < m;i++){
ima[sve[i]][0] = 0; ima[sve[i]][1] = 0;
g[sve[i]].clear();
}
return sol;
}
