#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<pair<int, int>> adjlist[500001];
int subsz[500001], level[500001], centpar[500001][20];
long long dist[500001][20], ans[500001];
vector<int> v;
void dfs(int x, int p) {
subsz[x] = 1;
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
dfs(i.first, x);
subsz[x] += subsz[i.first];
}
}
int centroid(int x, int p, int treesz) {
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
if (treesz < subsz[i.first] * 2) {
return centroid(i.first, x, treesz);
}
}
return x;
}
void dfs2(int x, int p, int l, int cent, long long cost) {
centpar[x][l] = cent;
dist[x][l] = cost;
for (auto i: adjlist[x]) {
if (i.first == p || level[i.first] != 0) {
continue;
}
dfs2(i.first, x, l, cent, cost + i.second);
}
}
void decomp(int x, int p, int l) {
dfs(x, -1);
int cent = centroid(x, -1, subsz[x]);
level[cent] = l;
dfs2(cent, -1, l, cent, 0);
for (auto i: adjlist[cent]) {
if (level[i.first] == 0) {
decomp(i.first, cent, l + 1);
}
}
}
void update(int x) {
for (int i = 1; i <= level[x]; i++) {
ans[centpar[x][i]] = min(ans[centpar[x][i]], dist[x][i]);
v.push_back(centpar[x][i]);
}
}
long long query(int x) {
long long ans2 = LLONG_MAX;
for (int i = 1; i <= level[x]; i++) {
if (ans[centpar[x][i]] == LLONG_MAX) {
continue;
}
ans2 = min(ans2, ans[centpar[x][i]] + dist[x][i]);
}
return ans2;
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
adjlist[A[i]].push_back({B[i], D[i]});
adjlist[B[i]].push_back({A[i], D[i]});
}
decomp(0, -1, 1);
for (int i = 0; i < N; i++) {
ans[i] = LLONG_MAX;
}
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
update(X[i]);
}
long long ans2 = LLONG_MAX;
for (int i = 0; i < T; i++) {
ans2 = min(ans2, query(Y[i]));
}
for (auto i: v) {
ans[i] = LLONG_MAX;
}
v.clear();
return ans2;
}
