#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <iomanip>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
const ll INF = 1e18;
vvpll tree;
vll is_removed;
vll sz;
vpll min_dist;
vvpll ancestors;
ll num_query = 0;
ll get_centroid(ll node, ll papa, ll cur_sz) {
for (auto& it : tree[node]) {
ll nei = it.first;
if (nei == papa || is_removed[nei]) continue;
if (sz[nei] > cur_sz / 2) {
return get_centroid(nei, node, cur_sz);
}
}
return node;
}
ll get_subtree_size(ll node, ll papa) {
sz[node] = 1;
for (auto& it : tree[node]) {
ll nei = it.first;
if (nei == papa || is_removed[nei]) continue;
sz[node] += get_subtree_size(nei, node);
}
return sz[node];
}
void get_dists(ll node, ll centroid, ll papa, ll cur_dist) {
for (auto& it : tree[node]) {
ll nei = it.first, w = it.second;
if (nei == papa || is_removed[nei]) continue;
get_dists(nei, centroid, node, cur_dist + w);
}
ancestors[node].push_back({ centroid, cur_dist });
}
void centroid_decomp(ll node) {
ll cur_sz = get_subtree_size(node, -1);
ll centroid = get_centroid(node, -1, cur_sz);
is_removed[centroid] = true;
for (auto& it : tree[centroid]) {
ll nei = it.first, w = it.second;
if (is_removed[nei]) continue;
get_dists(nei, centroid, centroid, w);
centroid_decomp(nei);
}
}
void update(ll node) {
min_dist[node] = { 0, num_query };
rep(i, 0, ancestors[node].size()) {
ll ancestor = ancestors[node][i].first;
ll dist = ancestors[node][i].second;
//upmin(min_dist[ancestor].first, dist);
min_dist[ancestor] = { min(min_dist[ancestor].first, dist), num_query };
}
}
ll query(ll node) {
ll res = min_dist[node].first;
if (min_dist[node].second != num_query) res = INF;
rep(i, 0, ancestors[node].size()) {
ll ancestor = ancestors[node][i].first;
ll dist = ancestors[node][i].second;
if (min_dist[ancestor].second == num_query) upmin(res, min_dist[ancestor].first + dist);
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
ll n = N;
num_query = 0;
tree.clear(), tree.resize(n);
is_removed.clear(), is_removed.resize(n);
sz.clear(), sz.resize(n);
ancestors.clear(), ancestors.resize(n);
min_dist.clear(), min_dist.resize(n, INF);
rep(i, 0, n - 1) {
ll a, b, c;
a = A[i], b = B[i], c = D[i];
tree[a].push_back({ b, c });
tree[b].push_back({ a, c });
}
centroid_decomp(0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll sz_a = S, sz_b = T;
ll ans = INF;
rep(i, 0, sz_a) {
ll node = X[i];
update(node);
}
rep(i, 0, sz_b) {
ll node = Y[i];
upmin(ans, query(node));
}
//fill(min_dist.begin(), min_dist.end(), INF);
num_query++;
return ans;
}
