#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<bool, bool> pbb;
namespace {
const int MXN = 500005, LG = 20;
const ll INF = 3.9e18;
int n;
vector<pii> edge[MXN];
int p[LG][MXN], d[MXN], C;
pii dfn[MXN];
ll s[LG][MXN];
pbb clr[MXN];
struct VSET {
bitset<MXN> b;
vector<int> v;
void clear() {
for (auto &i : v) b[i] = 0;
v.clear();
}
void insert(int x) {
if (b[x]) return;
b[x] = true;
v.push_back(x);
}
} vs;
void ADD_EDGE(int x, int y, int w) {
edge[x].push_back(mp(w, y));
edge[y].push_back(mp(w, x));
}
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
dfn[id].fs = C++;
for (auto &[w, i] : edge[id]) {
if (i == par) continue;
s[0][i] = w;
DFS(i, id, dep + 1);
}
dfn[id].sc = C;
}
void INIT() {
DFS(1, 0, 0);
FOR(w, 1, LG) {
FOR(id, 1, n + 1) {
p[w][id] = p[w - 1][p[w - 1][id]];
s[w][id] = s[w - 1][id] + s[w - 1][p[w - 1][id]];
}
}
}
int LEAP(int x, int k) {
FOR(w, 0, LG) {
if (k & (1 << w)) x = p[w][x];
}
return x;
}
int LCA(int x, int y) {
// debug(x, y);
if (d[x] < d[y]) swap(x, y);
x = LEAP(x, d[x] - d[y]);
if (x == y) {
// debug(x);
return x;
}
for (int w = LG - 1; w >= 0; w--) {
if (p[w][x] == p[w][y]) continue;
x = p[w][x];
y = p[w][y];
}
// debug(p[0][x]);
return p[0][x];
}
ll LEN(int r, int x) {
int dai = d[x] - d[r];
ll ans = 0;
FOR(w, 0, LG) {
if (dai & (1 << w)) {
ans += s[w][x];
x = p[w][x];
}
}
return ans;
}
namespace VTREE {
vector<pli> edge[MXN];
pll rb[MXN];
void BUILD(vector<pii> &nd) {
sort(nd.begin(), nd.end());
// for (auto [_, i] : nd) cout << i << ' ';
// cout << endl;
vector<int> st;
st.push_back(1);
for (auto [_, i] : nd) {
if (i == 1) continue;
while (st.size()) {
int p = st.back();
if (!(dfn[i].sc <= dfn[p].sc)) st.pop_back();
else break;
}
int p = st.back();
// debug(p, i);
edge[p].push_back(mp(LEN(p, i), i));
st.push_back(i);
}
}
ll DFS(int id) {
// debug(id);
ll ans = INF;
rb[id] = mp(INF, INF);
if (clr[id].fs) rb[id].fs = 0;
if (clr[id].sc) rb[id].sc = 0;
for (auto [len, i] : edge[id]) {
ans = min(ans, DFS(i));
rb[id].fs = min(rb[id].fs, rb[i].fs + len);
rb[id].sc = min(rb[id].sc, rb[i].sc + len);
}
return min(ans, rb[id].fs + rb[id].sc);
}
void CLEAR(vector<pii> &nd) {
for (auto &[_, i] : nd) {
edge[i].clear();
}
}
}
ll QUERY() {
{
vector<pii> dist;
for (auto &i : vs.v) dist.push_back(mp(dfn[i].fs, i));
sort(dist.begin(), dist.end());
FOR(i, 1, dist.size()) {
vs.insert(LCA(dist[i - 1].sc, dist[i].sc));
}
vs.insert(1);
}
ll ans;
{
vector<pii> nd;
for (auto &i : vs.v) nd.push_back(mp(dfn[i].fs, i));
VTREE::BUILD(nd);
ans = VTREE::DFS(1);
VTREE::CLEAR(nd);
}
return ans;
}
}
void Init(int N, int A[], int B[], int D[]) {
::n = N;
FOR(i, 0, N - 1) ADD_EDGE(A[i] + 1, B[i] + 1, D[i]);
INIT();
}
long long Query(int S, int X[], int T, int Y[]) {
FOR(i, 0, S) {
vs.insert(X[i] + 1);
clr[X[i] + 1].fs = 1;
}
FOR(i, 0, T) {
vs.insert(Y[i] + 1);
clr[Y[i] + 1].sc = 1;
}
ll ans = QUERY();
for (auto &i : vs.v) {
clr[i] = mp(false, false);
}
vs.clear();
return ans;
}
