#include <bits/stdc++.h>
#include "factories.h"
const int N = 5000 +5;
#define pii pair<int,int>
#define se second
#define fi first
#define ll long long
#define pb push_back
const ll INF = 2e18;
using namespace std;
vector<vector<pii>> adj(N);
int tin[N],tout[N];
int tt=0;
int par[N][20];
ll dist[N];
void dfs(int s,int p){
tin[s] = ++tt;
par[s][0] = p;
for(int i=1; i<20;i++){
par[s][i] = par[par[s][i-1]][i-1];
}
for(auto& i : adj[s]){
if(i.fi!=p){
dist[i.fi] = dist[s]+i.se;
dfs(i.fi,s);
}
}
tout[s] = tt;
}
void Init(int n, int A[], int B[], int D[]) {
for(int i=0;i<n-1;i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
dist[0]=0;
dfs(0,0);
}
bool isanc(int u, int v){
return (tin[u]<=tin[v] && tout[u]>=tin[v]);
}
int lca(int u,int v){
if(isanc(u,v)) return u;
if(isanc(v,u)) return v;
for(int i=20;i>=0;i--){
if(!isanc(par[u][i],v))
u = par[u][i];
}
return par[u][0];
}
vector<vector<pair<ll,ll>>> gvt(N);
void connect(int u, int v){
if(u==v)
return;
ll d =abs(dist[u]-dist[v]);
gvt[u].pb({v,d});
gvt[v].pb({u,d});
}
int createvt(vector<int>& nodes){
sort(nodes.begin(),nodes.end(),[](int& u, int& v){
return tin[u] < tin[v];
});
for(int i = int(nodes.size())-2;i>=0;i--){
nodes.pb(lca(nodes[i],nodes[i+1]));
}
sort(nodes.begin(),nodes.end(),[](int& u, int& v){
return tin[u] < tin[v];
});
vector<int> ve;
ve.pb(nodes[0]);
for(int i=1;i<nodes.size();i++){
while(!isanc(ve.back(),nodes[i])){
connect(ve.back(),ve[ve.size()-2]);
ve.pop_back();
}
ve.pb(nodes[i]);
}
while(ve.size()>1){
connect(ve.back(),ve[ve.size()-2]);
ve.pop_back();
}
return ve[0];
}
ll best=INF;
int col[N];
pair<ll,ll> defes(int u, int p){
ll m1 = (col[u] == 1 ? 0 : INF), m2 = (col[u]==2 ? 0 : INF);
for(auto& v : gvt[u]){
if(p==v.fi) continue;
pair<ll,ll> sigma = defes(v.fi,u);
m1=min(sigma.fi+v.se,m1),m2=min(sigma.se+v.se,m2);
}
best =min(m1+m2,best);
return {m1,m2};
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> nodes;
for(int i = 0;i < S;i++)
col[X[i]] = 1,nodes.pb(X[i]);
for(int i = 0;i < T;i++)
col[Y[i]] = 2,nodes.pb(Y[i]);
best = INF;
int ligma = createvt(nodes);
defes(ligma,ligma);
for(int i = 0;i < S;i++)
col[X[i]] = 0;
for(int i = 0;i < T;i++)
col[Y[i]] = 0;
for(auto& i : nodes){
gvt[i].clear();
}
return best;
return 0;
}
