#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long i64;
const int MAX_N = 500000 + 5;
const int MAX_K = 20;
const i64 INF = 1e18;
int Time = 0;
vector<pair<int, int>> g[MAX_N];
int sub[MAX_N], del[MAX_N], par[MAX_N], in[MAX_N], pw[MAX_K], L[2 * MAX_N];
vector<vector<int>> table(2 * MAX_N, vector<int>(MAX_K));
vector<int> depth(MAX_N);
i64 d[MAX_N], best_way[MAX_N];
int calc_subtree(int node, int p) {
sub[node] = 1;
for (auto to : g[node]) {
if (to.first != p && !del[to.first]) {
sub[node] += calc_subtree(to.first, node);
}
}
return sub[node];
}
int calc_centroid(int node, int p, const int tam) {
for (auto to : g[node]) {
if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
return calc_centroid(to.first, node, tam);
}
}
return node;
}
void decompose(int node, int p) {
const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
del[centroid] = 1;
par[centroid] = p;
for (auto to : g[centroid]) {
if (!del[to.first]) {
decompose(to.first, centroid);
}
}
}
vector<int> euler;
void prep(int node, int p) {
in[node] = Time++;
euler.emplace_back(node);
for (auto to : g[node]) {
if (to.first != p) {
d[to.first] = d[node] + to.second;
depth[to.first] = depth[node] + 1;
prep(to.first, node);
euler.emplace_back(node);
Time++;
}
}
}
void build_lca() {
const int n = euler.size();
for (int i = 0; i < n; i++) {
table[i][0] = euler[i];
}
for (int i = 1; i <= n; i++) {
L[i] = log2(i);
}
for (int j = 1; j < MAX_K; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
int H1 = depth[table[i][j - 1]];
int H2 = depth[table[i + (1 << (j - 1))][j - 1]];
table[i][j] = (H1 < H2 ? table[i][j - 1] : table[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int lca(int u, int v) {
if (u == v) return u;
if (in[u] > in[v]) {
swap(u, v);
}
const int st = in[u];
const int et = in[v];
const int k = L[(et - st + 1)];
return (depth[table[st][k]] < depth[table[et - pw[k] + 1][k]] ? table[st][k] : table[et - pw[k] + 1][k]);
}
i64 get_dist(int u, int v) {
return d[u] + d[v] - 2LL * d[lca(u, v)];
}
void paint(int node, bool reset) {
int start_location = node;
while(node != -1) {
if (reset) {
best_way[node] = INF;
} else {
best_way[node] = min(best_way[node], get_dist(start_location, node));
}
node = par[node];
}
}
i64 solve(int node) {
int start_location = node;
i64 mn = INF;
while(node != -1) {
mn = min(mn, get_dist(start_location, node) + best_way[node]);
node = par[node];
}
return mn;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
const int st = A[i];
const int et = B[i];
const int w = D[i];
g[st].emplace_back(et, w);
g[et].emplace_back(st, w);
}
prep(0, -1);
for (int i = 0; i < MAX_K; i++) {
pw[i] = (1 << i);
}
build_lca();
decompose(0, -1);
for (int i = 0; i < MAX_N; i++) {
best_way[i] = INF;
}
}
i64 Query(int S, int X[], int T, int Y[]) {
i64 mn = INF;
if (S > T) {
swap(S, T);
swap(X, Y);
}
for (int i = 0; i < S; i++) {
paint(X[i], false);
}
for (int i = 0; i < T; i++) {
mn = min(mn, solve(Y[i]));
}
for (int i = 0; i < S; i++) {
paint(X[i], true);
}
return mn;
}
