#include <bits/stdc++.h>
using namespace std;
#include "factories.h"
#define distance _distance
using ll = long long;
using ii = pair<int, int>;
namespace {
struct Edge{
int to;
ll d;
};
// Main variables
const ll inf = 1e18;
int n, lg, timer;
vector<int> depth, tin, tout;
vector<ll> distance;
vector<vector<int>> parent;
vector<vector<Edge>> adj;
// Main functions
void dfs(int x, int p = -1, int d = 0, ll dist = 0){
depth[x] = d;
distance[x] = dist;
tin[x] = timer++;
parent[0][x] = (p < 0) ? x : p;
for (auto edge: adj[x]){
int k = edge.to;
if (k == p) continue;
dfs(k, x, d + 1, dist + edge.d);
}
tout[x] = timer;
}
int LCA(int x, int y){
if (depth[x] > depth[y]) swap(x, y);
for (int j = lg-1; j >= 0; j--){
if (depth[y] - (1 << j) >= depth[x]){
y = parent[j][y];
}
}
if (x == y) return x;
for (int j = lg-1; j >= 0; j--){
if (parent[j][x] != parent[j][y]){
x = parent[j][x];
y = parent[j][y];
}
}
return parent[0][x];
}
// Query variables
vector<int> reset_queue;
vector<int> color;
vector<vector<int>> graph;
// Query functions
vector<ll> solve(ll &res, int x, int p = -1){
vector<ll> mindist(2, inf);
if (color[x] >= 0) mindist[color[x]] = 0;
for (auto k: graph[x]){
if (k == p) continue;
auto subdist = solve(res, k, x);
for (int j = 0; j < 2; j++){
mindist[j] = min(mindist[j], subdist[j] + distance[k] - distance[x]);
}
}
res = min(res, mindist[0] + mindist[1]);
return mindist;
}
}
void Init(int N, int A[], int B[], int D[]){
// Initialize
n = N;
lg = 31 - __builtin_clz(n) + 1;
timer = 0;
depth.resize(n);
tin.resize(n);
tout.resize(n);
distance.resize(n);
parent.assign(lg, vector<int>(n));
adj.resize(n);
color.assign(n, -1);
graph.resize(n);
for (int i = 0; i < n; i++){
int a = A[i], b = B[i], d = D[i];
adj[a].push_back(Edge{b, d});
adj[b].push_back(Edge{a, d});
}
// DFS
dfs(0);
for (int j = 1; j < lg; j++){
for (int i = 0; i < n; i++){
parent[j][i] = parent[j-1][parent[j-1][i]];
}
}
}
ll Query(int A, int X[], int B, int Y[]){
// Construct the virtual tree
// Find all virtual tree nodes
vector<int> nodes;
for (int i = 0; i < A; i++){
nodes.push_back(X[i]);
color[X[i]] = 0;
}
for (int i = 0; i < B; i++){
nodes.push_back(Y[i]);
color[Y[i]] = 1;
}
auto sort_by_tin = [&](int p1, int p2){
return tin[p1] < tin[p2];
};
sort(nodes.begin(), nodes.end(), sort_by_tin);
int sz = nodes.size();
for (int i = 1; i < sz; i++){
nodes.push_back(LCA(nodes[i-1], nodes[i]));
}
sort(nodes.begin(), nodes.end(), sort_by_tin);
nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
sz = nodes.size();
for (auto i: nodes) reset_queue.push_back(i);
// Construct the tree
stack<int> stk;
for (int i = 0; i < sz; i++){
int x = nodes[i];
while (!stk.empty() && tout[x] > tout[stk.top()]) stk.pop();
if (!stk.empty()){
int p = stk.top();
graph[p].push_back(x);
graph[x].push_back(p);
}
stk.push(x);
}
// Solve the query
ll res = inf;
solve(res, nodes[0]);
// Reset
for (auto x: reset_queue){
graph[x].clear();
color[x] = -1;
}
reset_queue.clear();
return res;
}
#undef distance
