#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
constexpr int NMAX = 5e5 + 5;
typedef long long LL;
typedef pair <int, LL> PIL;
vector <PIL> G[NMAX];
vector <PIL> Root[NMAX];
bool viz[NMAX];
int Size[NMAX];
LL Dist[NMAX];
void Initial_Dfs (int Node, int dad = -1) {
Size[Node] = 1;
for (auto it : G[Node]) {
int to = it.first;
if (to == dad || viz[to]) continue;
Initial_Dfs(to, Node);
Size[Node] += Size[to];
}
}
int GetCentroid (int Node, int Sz, int dad = -1) {
int Max = Sz - Size[Node];
for (auto it : G[Node]) {
int to = it.first;
if (to == dad || viz[to]) continue;
int x = GetCentroid(to, Sz, Node);
if (x != 0) return x;
Max = max(Max, Size[to]);
}
if (Max <= (Sz + 1) / 2) return Node;
return 0;
}
void Add (int Node, int cent, LL dist, int dad = -1) {
Root[Node].push_back({cent, dist});
for (auto it : G[Node]) {
int to = it.first;
if (to == dad || viz[to]) continue;
Add(to, cent, dist + it.second, Node);
}
}
void CentroidDecomposition (int Node) {
Initial_Dfs(Node);
int centroid = GetCentroid(Node, Size[Node]);
Add(centroid, centroid, 0);
viz[centroid] = 1;
for (auto it : G[centroid]) {
int to = it.first;
if (!viz[to]) CentroidDecomposition(to);
}
}
void Init (int N, int A[], int B[], int D[]) {
for (int i = 0; i < N-1; ++ i ) {
++ A[i];
++ B[i];
G[A[i]].push_back({B[i], D[i]});
G[B[i]].push_back({A[i], D[i]});
}
CentroidDecomposition(1);
for (int i = 1; i <= N; ++ i )
Dist[i] = -1;
}
void Compute (int Node) {
for (auto it : Root[Node]) {
if (Dist[it.first] == -1) Dist[it.first] = it.second;
Dist[it.first] = min(Dist[it.first], it.second);
}
}
LL Minimum (int Node) {
LL ans = 1000000000000000;
for (auto it : Root[Node]) {
if (Dist[it.first] == -1) continue;
ans = min(ans, Dist[it.first] + it.second);
}
return ans;
}
void Delete (int Node) {
for (auto it : Root[Node])
Dist[it.first] = -1;
}
long long Query (int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++ i )
Compute(X[i]+1);
LL ans = 1000000000000000;
for (int i = 0; i < T; ++ i )
ans = min(ans, Minimum(Y[i]+1));
for (int i = 0; i < S; ++ i )
Delete(X[i] + 1);
return ans;
}
