#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)1e16;
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, ret = inf;
int tp, b, S[MX], N, Q;
struct info {
int v, tp;
ll d;
};
V<info> nd[MX];
struct cen_info {
pair<ll, int> h1{inf, 0}, h2{inf, 0};
};
V<cen_info> cd(MX);
V<PR<int>> g[MX];
bool is[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;
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]});
}
cen();
}
long long Query(int A, int a[], int B, int b[]) {
forn(i, A) {
int x = ++a[i];
is[x] = 1;
for(auto p : nd[x]) {
auto &f = cd[p.v].h1;
auto &s = cd[p.v].h2;
if(p.d < f.first) {
if(f.second != p.tp)swap(f, s);
f = {p.d, p.tp};
}
else if(p.d < s.first) {
if(p.tp != f.second)
s = {p.d, p.tp};
}
}
}
ret = inf;
forn(i, B) {
int x = ++b[i];
if(is[x])ret = 0;
for(auto p : nd[x]) {
auto &f = cd[p.v].h1;
auto &s = cd[p.v].h2;
if(is[p.v])ckmi(ret, p.d);
if(p.tp == f.second) {
ckmi(ret, p.d + s.first);
}
else ckmi(ret, p.d + f.first);
ckmi(ret, cd[x].h1.first);
}
}
forn(i, A) {
int x= a[i];
is[x] = 0;
for(auto p : nd[x]) {
cd[p.v].h1 = cd[p.v].h2 = {inf, 0};
}
}
return ret;
}
