#include "factories.h"
#include <vector>
struct Edge
{
Edge(int e, long long w) : end(e), weight(w) {}
int end;
long long weight;
};
const int MAXN = 5e5;
const int LOGN = 20;
const long long INFTY = 1e18;
std::vector<Edge> tree[MAXN];
bool seen[MAXN];
int size[MAXN];
int centrParent[MAXN], centrDepth[MAXN];
long long centrDist[MAXN][LOGN];
long long minActive[MAXN];
void calcsize(int node)
{
seen[node] = true;
size[node] = 1;
for (Edge& edge : tree[node])
if (!seen[edge.end])
{
calcsize(edge.end);
size[node] += size[edge.end];
}
seen[node] = false;
}
int findcentr(int node, int treesize)
{
if (seen[node])
return 0;
seen[node] = true;
int maxSubSize = treesize - size[node];
for (Edge &edge : tree[node])
{
int ans = findcentr(edge.end, treesize);
if (ans < 0)
{
seen[node] = false;
return ans;
}
maxSubSize = std::max(maxSubSize, ans);
}
seen[node] = false;
if (maxSubSize <= treesize / 2)
return (-1 - node);
return size[node];
}
void calcdist(int node, long long dist)
{
if (seen[node])
return;
seen[node] = true;
centrDist[node][centrDepth[node]] = dist;
centrDepth[node]++;
for (Edge &edge : tree[node])
calcdist(edge.end, dist + edge.weight);
seen[node] = false;
}
void buildcentr(int node, int parent)
{
calcsize(node);
int centroid = (-1 - findcentr(node, size[node]));
centrParent[centroid] = parent;
seen[centroid] = true;
for (Edge &edge : tree[centroid])
if (!seen[edge.end])
buildcentr(edge.end, centroid);
seen[centroid] = false;
calcdist(centroid, 0);
minActive[centroid] = INFTY;
}
void Init(int N, int A[], int B[], int D[])
{
for (int iEdge = 0; iEdge < N - 1; iEdge++)
{
tree[A[iEdge]].emplace_back(B[iEdge], D[iEdge]);
tree[B[iEdge]].emplace_back(A[iEdge], D[iEdge]);
}
buildcentr(0, -1);
}
long long Query(int S, int X[], int T, int Y[])
{
for (int iNode = 0; iNode < S; iNode++)
{
int ancester = X[iNode];
for (int iAnc = 0; iAnc < centrDepth[X[iNode]]; iAnc++)
{
minActive[ancester] = std::min(minActive[ancester], centrDist[X[iNode]][iAnc]);
ancester = centrParent[ancester];
}
}
long long minDist = INFTY;
for (int iNode = 0; iNode < T; iNode++)
{
int ancester = Y[iNode];
for (int iAnc = 0; iAnc < centrDepth[Y[iNode]]; iAnc++)
{
minDist = std::min(minDist, minActive[ancester] + centrDist[Y[iNode]][iAnc]);
ancester = centrParent[ancester];
}
}
for (int iNode = 0; iNode < S; iNode++)
for (int ancester = X[iNode]; ancester != -1; ancester = centrParent[ancester])
minActive[ancester] = INFTY;
return minDist;
}
