#include "factories.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
// Graf va yordamchi massivlar
vector<pair<int, int>> adj[500005];
int sz[500005], parent[500005];
bool visited[500005];
ll best_dist[500005];
// Masofalarni hisoblash uchun (LCA + Depth)
ll depth[500005];
int up[500005][20], tin[500005], tout[500005], timer;
// Daraxt xususiyatlarini aniqlash (DFS)
void dfs_lca(int u, int p, ll d) {
tin[u] = ++timer;
depth[u] = d;
up[u][0] = p;
for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
for (auto& edge : adj[u]) {
if (edge.first != p) dfs_lca(edge.first, u, d + edge.second);
}
tout[u] = timer;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int get_lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = 19; i >= 0; i--) {
if (!is_ancestor(up[u][i], v)) u = up[u][i];
}
return up[u][0];
}
ll get_dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[get_lca(u, v)];
}
// Sentroidni topish funksiyalari
int get_sz(int u, int p) {
sz[u] = 1;
for (auto& edge : adj[u]) {
if (edge.first != p && !visited[edge.first]) sz[u] += get_sz(edge.first, u);
}
return sz[u];
}
int get_centroid(int u, int p, int n) {
for (auto& edge : adj[u]) {
if (edge.first != p && !visited[edge.first] && sz[edge.first] > n / 2)
return get_centroid(edge.first, u, n);
}
return u;
}
void decompose(int u, int p) {
int n = get_sz(u, -1);
int centroid = get_centroid(u, -1, n);
visited[centroid] = true;
parent[centroid] = p;
for (auto& edge : adj[centroid]) {
if (!visited[edge.first]) decompose(edge.first, centroid);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs_lca(0, 0, 0);
decompose(0, -1);
for (int i = 0; i < N; i++) best_dist[i] = INF;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> modified_centroids;
// X to'plamini sentroid daraxtiga joylashtirish
for (int i = 0; i < S; i++) {
int curr = X[i];
while (curr != -1) {
best_dist[curr] = min(best_dist[curr], get_dist(X[i], curr));
modified_centroids.push_back(curr);
curr = parent[curr];
}
}
ll ans = INF;
// Y to'plami orqali eng qisqa masofani topish
for (int i = 0; i < T; i++) {
int curr = Y[i];
while (curr != -1) {
ans = min(ans, get_dist(Y[i], curr) + best_dist[curr]);
curr = parent[curr];
}
}
// Massivni tozalash
for (int c : modified_centroids) best_dist[c] = INF;
return ans;
}
