#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[z.se] > 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; } n = NN; for (int i = 0; i <= n - 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) { ll cur = dis(x, A[i]); if (cur < Min[x]) { if (Min[x] == 1e18) use.push_back(x); Min[x] = cur; } x = up[x]; } } ll ans = 1e18; for (int i = 0; i < two; ++i) { ++B[i]; x = B[i]; while (x != 0) { ll cur = dis(x, B[i]); ans = min(ans, cur + Min[x]); x = up[x]; } } for (int z: use) Min[z] = 1e18; return ans; }