#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)
using namespace std;
const int nax = 5e5 + 111;
int n;
vector <pair<int,int>> v[nax];
int par[nax];
int kil[nax];
int nn;
int siz[nax];
int LVL[nax];
ll odl[nax][20];
void dfs(int u, int p) {
nn++;
siz[u] = 1;
for(auto it : v[u])
if(it.fi != p && !kil[it.fi]) {
dfs(it.fi, u);
siz[u] += siz[it.fi];
}
}
int daj(int u, int p) {
for(auto it : v[u])
if(it.fi != p && !kil[it.fi] && nn <= 2 * siz[it.fi])
return daj(it.fi, u);
return u;
}
void getodl(int u, int p, int lvl) {
for(auto it : v[u])
if(it.fi != p && !kil[it.fi]) {
odl[it.fi][lvl] = odl[u][lvl] + it.se;
getodl(it.fi, u, lvl);
}
}
void decomp(int u, int p, int lvl = 0) {
nn = 0;
dfs(u, 0);
int C = daj(u, 0);
par[C] = p;
LVL[C] = lvl;
kil[C] = 1;
getodl(C, 0, lvl);
for(auto it : v[C])
if(!kil[it.fi])
decomp(it.fi, C, lvl + 1);
}
ll naj[nax];
void Init(int N, int a[], int b[], int c[]) {
n = N;
for(int i = 0; i < n; ++i)
a[i]++;
for(int i = 0; i < n; ++i)
b[i]++;
for(int i = 0; i < n - 1; ++i) {
v[a[i]].pb(mp(b[i], c[i]));
v[b[i]].pb(mp(a[i], c[i]));
}
decomp(1, 0);
for(int i = 1; i <= n; ++i)
naj[i] = 1e18;
}
ll Query(int s, int x[], int t, int y[]) {
for(int i = 0; i < s; ++i)
x[i]++;
for(int i = 0; i < t; ++i)
y[i]++;
ll res = 1e18;
for(int i = 0; i < s; ++i) {
int node = x[i];
while(node != 0) {
naj[node] = min(naj[node], odl[x[i]][LVL[node]]);
node = par[node];
}
}
for(int i = 0; i < t; ++i) {
int node = y[i];
while(node != 0) {
res = min(res, naj[node] + odl[y[i]][LVL[node]]);
node = par[node];
}
}
for(int i = 0; i < s; ++i) {
int node = x[i];
while(node != 0) {
naj[node] = 1e18;
node = par[node];
}
}
return res;
}
