#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
const int logn = 19;
int sub[500010];
int dp[20][500010];
int deg[500010];
long long dis[500010];
vector <pii> g[500010];
bool vis[500010];
int anc[500010];
long long aux[500010];
const long long inf = 1e16;
void dfs(int x, int par) {
dp[0][x] = par;
for(auto i : g[x]) {
if(i.first - par) {
deg[i.first] = 1 + deg[x];
dis[i.first] = i.second + dis[x];
dfs(i.first, x);
}
}
}
int lca(int p, int q) {
if(deg[p] > deg[q]) swap(p, q);
for(int i = logn; i >= 0; i--) {
if(deg[q] - (1 << i) >= deg[p]) {
q = dp[i][q];
}
}
if(p == q) return p;
for(int i = logn; i >= 0; i--) {
if(dp[i][p] != dp[i][q]) {
p = dp[i][p];
q = dp[i][q];
}
}
return dp[0][p];
}
long long distance(int p, int q) {
return dis[p] + dis[q] - (dis[lca(p, q)] << 1);
}
void subtree(int x, int par) {
sub[x] = 1;
for(auto i : g[x]) {
if(i.first != par && vis[i.first] == false) {
subtree(i.first, x);
sub[x] += sub[i.first];
}
}
}
int centroid(int x, int par, int range) {
for(auto i : g[x]) {
if(i.first != par && vis[i.first] == false) {
if(sub[i.first] > range) return centroid(i.first, x, range);
}
}
return x;
}
void create(int x, int par) {
subtree(x, 0);
int c = centroid(x, 0, sub[x] >> 1);
vis[c] = true;
anc[c] = par;
for(auto i : g[c]) {
if(vis[i.first] == false) {
create(i.first, c);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; i++) {
g[A[i]].push_back(pii(B[i], D[i]));
g[B[i]].push_back(pii(A[i], D[i]));
}
dfs(0, 0);
for(int i = 1; i <= logn; i++) {
for(int j = 0; j < N; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
create(0, -1);
for(int i = 0; i < N; i++) {
aux[i] = inf;
}
}
void put(int x) {
int cur = x;
while(cur >= 0) {
aux[cur] = min(aux[cur], distance(x, cur));
cur = anc[cur];
}
}
void remove(int x) {
int cur = x;
while(cur >= 0) {
aux[cur] = inf;
cur = anc[cur];
}
}
long long get(int x) {
int cur = x;
long long ans = inf;
while(cur >= 0) {
ans = min(ans, distance(x, cur) + aux[cur]);
cur = anc[cur];
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++) {
put(X[i]);
}
long long ans = inf;
for(int i = 0; i < T; i++) {
ans = min(ans, get(Y[i]));
}
for(int i = 0; i < S; i++) {
remove(X[i]);
}
return ans;
}
