/*
* Written by
* ______ _ _ ______ ____ ____ ____ ____
* |_ _|| |_| ||_ _||_ || __ || __ |/ _/
* | | | _ | | | / / || |||| ||| |__
* | | | | | | | | | |_ ||__||||__||\__ \
* |__| |_| |_| |__| |___||____||____|/____/
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define nmax 500500
template<class T>
struct segment_tree
{
int n;
T INF;
T st[nmax<<1];
segment_tree(T _INF): INF(_INF) {}
void init(const vector<T>& v)
{
n = v.size();
for(int i = 0; i < n; ++i)
st[i + n] = v[i];
for(int i = n - 1; i > 0; --i)
st[i] = min(st[i<<1], st[i<<1|1]);
}
T get(int l, int r)
{
T ans = INF;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) ans = min(ans, st[l++]);
if(r & 1) ans = min(ans, st[--r]);
}
return ans;
}
};
const ll INF = 1LL << 60LL;
int n, lv[nmax];
bool type[nmax];
ll ans, depth[nmax];
vector<int> adj[nmax], len[nmax];
vector<ii> el, ord, ord2, ord3;
segment_tree<ii> lca_tbl(ii(INT_MAX, 0)), st(ii(INT_MAX, 0));
int lca(int u, int v)
{
if(lv[u] > lv[v]) swap(u, v);
return lca_tbl.get(lv[u], lv[v] + 1).second;
}
void euler_tour(int u = 0, int p = -1, ll sum = 0)
{
depth[u] = sum;
lv[u] = el.size();
el.push_back(ii(lv[u], u));
for(int i = 0; i < adj[u].size(); ++i) {
if(adj[u][i] == p) continue;
euler_tour(adj[u][i], u, sum + len[u][i]);
el.push_back(ii(lv[u], u));
}
}
void Init(int _n, int a[], int b[], int d[])
{
n = _n;
for(int i = 0; i < n - 1; ++i) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
len[a[i]].push_back(d[i]);
len[b[i]].push_back(d[i]);
}
euler_tour();
lca_tbl.init(el);
}
pair<ll, ll> dfs(int l, int r, int rt)
{
if(l + 1 == r) {
ll dd = rt == -1 ? 0 : depth[ord[l].second] - depth[rt];
return type[ord[l].second] ? pair<ll, ll>(INF, dd)
: pair<ll, ll>(dd, INF);
}
int pos = st.get(l, r - 1).second;
pair<ll, ll> left = dfs(l, pos + 1, ord3[pos].second),
right = dfs(pos + 1, r, ord3[pos].second);
ll dd = rt == -1 ? 0 : depth[ord3[pos].second] - depth[rt];
ans = min(ans, min(left.first + right.second, left.second + right.first));
return pair<ll, ll>(dd + min(left.first, right.first), dd + min(left.second, right.second));
}
ll Query(int S, int X[], int T, int Y[])
{
ord.clear();
ord2.clear();
ord3.clear();
for(int i = 0; i < S; ++i) {
ord.push_back(ii(lv[X[i]], X[i]));
type[X[i]] = true;
}
for(int i = 0; i < T; ++i) {
ord.push_back(ii(lv[Y[i]], Y[i]));
type[Y[i]] = false;
}
sort(ord.begin(), ord.end());
for(int i = 0, x; i < ord.size() - 1; ++i) {
x = lca(ord[i].second, ord[i + 1].second);
ord2.push_back(ii(lv[x], i));
ord3.push_back(ii(lv[x], x));
}
st.init(ord2);
ans = INF;
dfs(0, ord.size(), -1);
return ans;
}
