#include "factories.h"
#include <bits/stdc++.h>
#include <ext/algorithm>
#include <ext/numeric>
using namespace std;
using namespace __gnu_cxx;
typedef long long ll;
const ll oo = 0x3f3f3f3f3f3f3f3f;
vector<vector<pair<int, ll>>> adj;
vector<vector<pair<ll, int>>> table;
vector<int> tour, in, out, id;
vector<ll> depth;
vector<bool> inA, inB;
void Init(int N, int A[], int B[], int D[])
{
adj.clear();
adj.resize(N);
for (int i = 0; i < N - 1; ++i)
{
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
tour.clear();
in = out = id = vector<int>(N);
depth = vector<ll>(N);
inA = inB = vector<bool>(N);
function<void(int, int, ll)> dfs = [&](int u, int p, ll d)
{
in[u] = tour.size();
depth[u] = d;
tour.push_back(u);
for (auto &e : adj[u])
if (e.first != p)
{
dfs(e.first, u, d + e.second);
tour.push_back(u);
}
out[u] = tour.size();
};
dfs(0, -1, 0);
int logn = __lg(tour.size());
table = vector<vector<pair<ll, int>>>(logn + 1, vector<pair<ll, int>>(tour.size()));
for (int i = 0; i < tour.size(); ++i)
table[0][i] = make_pair(depth[tour[i]], tour[i]);
for (int i = 0; i < logn; ++i)
for (int j = 0; j + (1 << i) < tour.size(); ++j)
table[i + 1][j] = min(table[i][j], table[i][j + (1 << i)]);
}
bool ancestor(int u, int v)
{
return in[u] <= in[v] && out[v] <= out[u];
};
int lca(int u, int v)
{
if (in[u] > in[v])
swap(u, v);
int l = __lg(in[v] - in[u]);
return u == v ? u : min(table[l][in[u]], table[l][in[v] - (1 << l)]).second;
};
long long Query(int S, int X[], int T, int Y[])
{
vector<int> v;
for (int i = 0; i < S; ++i)
inA[X[i]] = true, v.push_back(X[i]);
for (int i = 0; i < T; ++i)
inB[Y[i]] = true, v.push_back(Y[i]);
sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0, k = v.size(); i + 1 < k; ++i)
v.push_back(lca(v[i], v[i + 1]));
sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
v.erase(unique(v.begin(), v.end()), v.end());
vector<vector<pair<int, ll>>> tree(v.size());
vector<bool> A(v.size()), B(v.size());
for (int i = 0; i < v.size(); ++i)
id[v[i]] = i, A[i] = inA[v[i]], B[i] = inB[v[i]];
vector<int> stk, nonroot(v.size());
for (int &x : v)
{
while (!stk.empty() && !ancestor(stk.back(), x))
stk.pop_back();
if (!stk.empty())
{
nonroot[id[x]] = true;
tree[id[stk.back()]].push_back({id[x], depth[x] - depth[stk.back()]});
}
stk.push_back(x);
}
assert(count(nonroot.begin(), nonroot.end(), 0) == 1);
ll ans = oo;
function<pair<ll, ll>(int, ll)> go = [&](int u, ll d)
{
ll a = A[u] ? d : oo;
ll b = B[u] ? d : oo;
if (a != oo && b != oo)
ans = 0;
for (auto &e : tree[u])
{
pair<ll, ll> ch = go(e.first, d + e.second);
ans = min(ans, ch.first + b - 2 * d);
ans = min(ans, ch.second + a - 2 * d);
a = min(a, ch.first);
b = min(b, ch.second);
}
return make_pair(a, b);
};
go(0, 0);
for (int i = 0; i < S; ++i)
inA[X[i]] = false;
for (int i = 0; i < T; ++i)
inB[Y[i]] = false;
return ans;
}
