#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e18;
struct SegTree {
vector <ll> aint;
int n;
inline void init(int _n) {
n = _n;
aint.resize(4 * n + 1, INF);
}
inline void refresh(int nod) {
aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
}
void update(int nod, int left, int right, int pos, ll val) {
if(left == right) {
aint[nod] = val;
}
else {
int mid = (left + right) / 2;
if(pos <= mid) update(2 * nod, left, mid, pos, val);
else update(2 * nod + 1, mid + 1, right, pos, val);
refresh(nod);
}
}
ll query(int nod, int left, int right, int l, int r) {
if(l <= left && right <= r) {
return aint[nod];
}
else {
int mid = (left + right) / 2;
ll ans = INF;
if(l <= mid) ans = min(ans, query(2 * nod, left, mid, l, r));
if(mid < r) ans = min(ans, query(2 * nod + 1, mid + 1, right, l, r));
return ans;
}
}
}sta, stb;
vector < vector < pair <int, int> > > g;
vector <ll> dst;
vector <int> idl, idr, first, lvl, lg;
vector < vector <int> > rmq;
void dfs(int nod, int par, int &id, int &sz) {
lvl[nod] = lvl[par] + 1;
idl[nod] = ++id;
rmq[++sz][0] = nod;
first[nod] = sz;
for(auto it : g[nod]) {
if(it.first != par) {
dst[it.first] = dst[nod] + it.second;
dfs(it.first, nod, id, sz);
rmq[++sz][0] = nod;
}
}
idr[nod] = id;
}
int n;
void Init(int _n, int A[], int B[], int D[]) {
n = _n;
g.resize(n + 1);
int i;
for(i = 0; i < n - 1; i++) {
A[i]++, B[i]++;
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dst.resize(n + 1), idl.resize(n + 1), idr.resize(n + 1), first.resize(n + 1), lvl.resize(n + 1);
rmq.resize(2 * n + 1, vector <int>(20));
int id = 0, sz = 0;
dfs(1, 0, id, sz);
lg.resize(sz + 1);
for(i = 2; i <= sz; i++) {
lg[i] = lg[i >> 1] + 1;
}
for(int bit = 1; (1 << bit) <= sz; bit++) {
for(i = 1; i + (1 << bit) <= sz + 1; i++) {
int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];
if(lvl[a] < lvl[b]) {
rmq[i][bit] = a;
}
else {
rmq[i][bit] = b;
}
}
}
sta.init(n), stb.init(n);
}
inline int get(int x, int y) {
x = first[x], y = first[y];
if(x > y) swap(x, y);
int bit = lg[y - x + 1];
if(lvl[rmq[x][bit]] < lvl[rmq[y - (1 << bit) + 1][bit]]) {
return rmq[x][bit];
}
return rmq[y - (1 << bit) + 1][bit];
}
ll Query(int S, int X[], int T, int Y[]) {
int i;
for(i = 0; i < S; i++) {
X[i]++;
sta.update(1, 1, n, idl[X[i]], dst[X[i]]);
}
for(i = 0; i < T; i++) {
Y[i]++;
stb.update(1, 1, n, idl[Y[i]], dst[Y[i]]);
}
static vector <int> nodes;
nodes.clear();
for(i = 0; i < S; i++) {
nodes.push_back(X[i]);
}
for(i = 0; i < T; i++) {
nodes.push_back(Y[i]);
}
sort(nodes.begin(), nodes.end(), [&](const int &a, const int &b) {
return idl[a] < idl[b];
});
ll ans = INF;
for(i = 0; i + 1 < nodes.size(); i++) {
int nod = get(nodes[i], nodes[i + 1]);
ans = min(ans, sta.query(1, 1, n, idl[nod], idr[nod]) + stb.query(1, 1, n, idl[nod], idr[nod]) - 2 * dst[nod]);
}
for(i = 0; i < S; i++) {
sta.update(1, 1, n, idl[X[i]], INF);
}
for(i = 0; i < T; i++) {
stb.update(1, 1, n, idl[Y[i]], INF);
}
return ans;
}
