#include "factories.h"
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define li pair <ll, int>
#define fi first
#define se second
const int N = 5e5 + 10;
const int M = 1e6 + 10;
int n, q;
int x, y, w;
int in[N], out[N], pos[N], nd[N], tim;
int E[M][22], Log2[M], cnt;
int sz[N], up[N];
bool solved[N];
ll depth[N], Min[N];
vector <li> v[N];
void DFS(int s = 1, int p = -1) {
pos[s] = ++tim;
nd[tim] = s;
E[++cnt][0] = pos[s];
in[s] = cnt;
for (li z: v[s]) {
if (z.se == p) continue;
depth[z.se] = depth[s] + z.fi;
DFS(z.se, s);
E[++cnt][0] = pos[s];
}
out[s] = cnt;
}
int LCA(int A, int B) {
if (in[A] > in[B]) swap(A, B);
int k = Log2[out[B] - in[A] + 1];
return nd[min(E[in[A]][k], E[out[B] - (1 << k) + 1][k])];
}
ll dis(int A, int B) {
return depth[A] + depth[B] - 2 * depth[LCA(A, B)];
}
int calc_size(int s, int p = -1) {
sz[s] = 1;
for (li z: v[s]) {
if (z.se == p || solved[z.se]) continue;
sz[s] += calc_size(z.se, s);
}
return sz[s];
}
int FindCentroid(int s, int Size, int p = -1) {
for (li z: v[s]) {
if (z.se == p || solved[z.se]) continue;
if (sz[s] > Size) return FindCentroid(z.se, Size, s);
}
return s;
}
int BuildCetroidTree(int s = 1) {
int cen = FindCentroid(s, calc_size(s) >> 1);
solved[cen] = true;
Min[cen] = 1e18;
for (li z: v[cen]) {
if (solved[z.se]) continue;
up[BuildCetroidTree(z.se)] = cen;
}
return cen;
}
void Init(int NN, int A[], int B[], int D[]) {
for (int i = 2; i < M; ++i) {
Log2[i] = Log2[i >> 1] + 1;
}
for (int i = 0; i <= NN - 2; ++i) {
++A[i]; ++B[i];
v[A[i]].push_back(li(D[i], B[i]));
v[B[i]].push_back(li(D[i], A[i]));
}
DFS();
for (int j = 1; (1 << j) <= cnt; ++j) {
for (int i = 1; i + (1 << j) - 1 <= cnt; ++i) {
E[i][j] = min(E[i][j - 1], E[i + (1 << (j - 1))][j - 1]);
}
}
BuildCetroidTree();
}
ll Query(int one, int A[], int two, int B[]) {
vector <int> use;
for (int i = 0; i < one; ++i) {
++A[i];
x = A[i];
while (x != 0) {
Min[x] = min(Min[x], dis(x, A[i]));
use.push_back(x);
x = up[x];
}
}
ll ans = 1e18;
for (int i = 0; i < two; ++i) {
++B[i];
x = B[i];
while (x != 0) {
ans = min(ans, dis(x, B[i]) + Min[x]);
x = up[x];
}
}
for (int z: use) Min[z] = 1e18;
return ans;
}
