// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define nl '\n'
using ll = long long;
using E = array<int, 2>;
const int nax = 5e5+5;
const int LG = 20;
vector<E> adj[nax];
bool vis[nax];
int up[nax][LG];
int par[nax], siz[nax], dep[nax];
ll dx[nax], dy[nax], dst[nax];
const ll INFL = ll(1e18) + 10;
// START OF CENTROID DECOMPOSITION
int find_size(int u, int p = -1) {
if (vis[u]) return 0;
siz[u] = 1;
for(auto e : adj[u]) {
auto [v, w] = e;
if (v == p) continue;
siz[u] += find_size(v, u);
}
return siz[u];
}
int find_centroid(int u, int p, int n) {
for(auto e : adj[u]) {
auto [v, w] = e;
if (v == p) continue;
if (!vis[v] && siz[v] > n / 2) return find_centroid(v, u, n);
}
return u;
}
void init_centroid(int u = 0, int p = -1) {
find_size(u);
int c = find_centroid(u, -1, siz[u]);
vis[c] = 1;
par[c] = p;
// cout << c << " -> " << p << endl;
for(auto e : adj[c]) {
auto [v, wv] = e;
if (vis[v]) continue;
init_centroid(v, c);
}
}
// END OF CENTROID DECOMPOSITION
// START OF LCA
void dfs(int u = 0, int p = -1) {
up[u][0] = (p == -1 ? u : p);
for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];
for(auto e : adj[u]) {
auto [v, w] = e;
if (v == p) continue;
dst[v] = dst[u] + w;
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int jmp(int u, int d) {
for(int i = 0; i < LG; i++) if ((d>>i) & 1) u = up[u][i];
return u;
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
b = jmp(b, dep[b] - dep[a]); if (a == b) return a;
for(int i = LG - 1; i >= 0; i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
return up[a][0];
}
ll dist(int u, int v) {
return dst[u] + dst[v] - 2LL * dst[lca(u, v)];
}
// END OF LCA
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N; i++) {
vis[i] = 0; par[i] = -1;
dx[i] = dy[i] = INFL;
adj[i] = {};
dst[i] = dep[i] = siz[i] = 0;
for(int j = 0; j < LG; j++) up[i][j] = 0;
}
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]});
}
init_centroid();
dfs();
}
ll Query(int S, int X[], int T, int Y[]) {
vector<int> alt;
for(int i = 0; i < S; i++) {
int u = X[i];
// cout << u << endl;
dx[u] = 0; alt.push_back(u);
while(par[u] != -1) {
// cout << "PARS: " << u << endl;
alt.push_back(u = par[u]);
dx[u] = min(dx[u], dist(u, X[i]));
}
// cout << "PARS: " << u << endl;
}
for(int i = 0; i < T; i++) {
int u = Y[i];
// cout << u << endl;
dy[u] = 0; alt.push_back(u);
while(par[u] != -1) {
// cout << "PART: " << u << endl;
alt.push_back(u = par[u]);
dy[u] = min(dy[u], dist(u, Y[i]));
}
// cout << "PART: " << u << endl;
}
sort(begin(alt), end(alt)); alt.erase(unique(begin(alt), end(alt)), end(alt));
ll ans = INFL;
for(auto u : alt) {
// cout << u << " " << dx[u] << " + " << dy[u] << endl;
ans = min(ans, dx[u] + dy[u]);
dx[u] = dy[u] = INFL;
}
return ans;
}
