#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define R0F(i,b) ROF(i,0,b)
#define all(x) begin(x),end(x)
#define sz(x) int(x.size())
#define pb push_back
#define rsz resize
#define trav(a,x) for(auto&a :x)
#define fi first
#define se second
int const N=1e5+3;
// whether a node is visited, identify by id
bitset<2*N>vis;
vpi adj[2*N];
ll dp[2*N][2];
bool isleaf(int now,int par)
{
// guaranteed tree size >1
if(sz(adj[now])==1 && adj[now][0].fi==par)return 1;
return 0;
}
void dfs(int now,int par,int w)
{
trav(chi,adj[now])
{
if(chi.fi==par)continue;
dfs(chi.fi,now,chi.se);
}
dp[now][1]=w;
if(isleaf(now,par))dp[now][1]=-2e18;
trav(chi,adj[now])
{
if(chi.fi==par)continue;
dp[now][1]+=dp[chi.fi][0];
}
dp[now][0]=0;
trav(chi,adj[now])
{
if(chi.fi==par)continue;
dp[now][0]+=max(dp[chi.fi][1],dp[chi.fi][0]);
}
}
ll min_total_length(vi r, vi b) {
priority_queue<pair<int,pii>>q;
q.push({0,{0,-1}});
ll sum=0;
while(!q.empty())
{
int w1 = -q.top().fi;
int u = q.top().se.fi;
int par = q.top().se.se;
q.pop();
if(vis[u])continue;
vis[u]=1;
sum+=w1;
if(par!=-1)
{
adj[par].pb({u,w1});
adj[u].pb({par,w1});
}
if(u>=sz(r))
{
// blue
F0R(i,sz(r))
{
if(vis[i])continue;
int w = abs(b[u-sz(r)]-r[i]);
q.push({-w,{i,u}});
}
}
else
{
// red
F0R(i,sz(b))
{
if(vis[i+sz(r)])continue;
int w = abs(r[u]-b[i]);
q.push({-w,{i+sz(r),u}});
}
}
}
dfs(0,-1,0);
return sum-dp[0][0];
}
