#include "factories.h"
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
const int INF = 1e9 + 1;
const int MX = 5e5 + 100;
const ll inf = (ll)1e18;
const double eps = 1e-7;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
return (x > y ? x = y, 1 : 0);
}
bool R[MX];
ll d;
int tp, b, S[MX], N;
struct info {
int v, tp;
ll d;
};
V<info> nd[MX];
V<PR<int>> cd(MX);
V<PR<int>> g[MX];
V<ll> mi(MX);
int dfs_sz(int v, int p = -1) {
S[v] = 1;
for(auto [c, w] : g[v]) {
if(c == p || R[c])continue;
S[v] += dfs_sz(c, v);
}
return S[v];
}
int get_cen(int v, int ms, int p = -1) {
for(auto [c, w] : g[v])
if(c != p && !R[c] && S[c] * 2 > ms)
return get_cen(c, ms, v);
return v;
}
void dfs1(int v, int p) {
for(auto [c, w] : g[v]) {
if(c != p && !R[c]) {
d += w;
dfs1(c, v);
d -= w;
}
}
nd[v].push_back({b, tp, d});
}
void cen(int v = 1) {
v = get_cen(v, dfs_sz(v));
R[v] = 1;
nd[v].push_back({v, v, 0});
for(auto [c, w] : g[v]) {
if(!R[c]) {
b = v;
tp = c;
d = w;
dfs1(c, v);
}
}
for(auto [c, w] : g[v]) {
if(!R[c])
cen(c);
}
}
void Init(int _N, int a[], int b[], int c[]) {
N = _N;
forn(i, N - 1) {
++a[i], ++b[i];
g[a[i]].push_back({b[i], c[i]});
g[b[i]].push_back({a[i], c[i]});
}
forn(i, N) mi[i] = inf;
cen();
}
long long Query(int A, int a[], int B, int b[]) {
forn(i, A) a[i]++;
forn(i, B) b[i]++;
V<int> del;
forn(i, A) {
int x = a[i];
for(auto p : nd[x]) {
ckmi(mi[p.v], p.d);
del.push_back(p.v);
}
}
ll ret = inf;
forn(i, B) {
int x = b[i];
for(auto p : nd[x]) {
ckmi(ret, mi[p.v] + p.d);
}
}
for(auto c : del) mi[c] = inf;
assert(ret != inf);
return ret;
}
