#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
vector<vector<pair<int, long>>> adj, gr;
vector<int> sub;
vector<bool> done;
vector<long> dp;
} // namespace
int subtree(int u, int p)
{
sub[u] = 1;
for (auto [v, d] : adj[u])
{
if (v != p && !done[v])
sub[u] += subtree(v, u);
}
return sub[u];
}
int get_centroid(int sz, int u, int p)
{
for (auto [v, d] : adj[u])
{
if (v != p && !done[v])
{
if (sub[v] * 2 > sz)
return get_centroid(sz, v, u);
}
}
return u;
}
void dfs(int r, int u, int p, long dist)
{
gr[u].emplace_back(r, dist);
for (auto [v, d] : adj[u])
{
if (v != p && !done[v])
dfs(r, v, u, dist + d);
}
}
void rec(int u)
{
int cen = get_centroid(subtree(u, -1), u, -1);
dfs(cen, cen, -1, 0);
done[cen] = 1;
for (auto [v, d] : adj[cen])
{
if (!done[v])
rec(v);
}
}
void upd(int u)
{
for (auto [r, dist] : gr[u])
dp[r] = min(dp[r], dist);
}
long qry(int u)
{
long x = LONG_MAX;
for (auto [r, dist] : gr[u])
{
if (dp[r] != LONG_MAX)
x = min(x, dist + dp[r]);
}
return x;
}
void reset(int u)
{
for (auto [r, dist] : gr[u])
dp[r] = LONG_MAX;
}
void Init(int N, int A[], int B[], int D[])
{
adj.assign(N, vector<pair<int, long>>());
for (int i = 0; i < N - 1; i++)
{
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
sub.assign(N, 0);
done.assign(N, 0);
gr.assign(N, vector<pair<int, long>>());
rec(0);
dp.assign(N, LONG_MAX);
}
long long Query(int S, int X[], int T, int Y[])
{
for (int i = 0; i < S; i++)
upd(X[i]);
long cost = LONG_MAX;
for (int i = 0; i < T; i++)
cost = min(cost, qry(Y[i]));
for (int i = 0; i < S; i++)
reset(X[i]);
return cost;
}
