#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define mp make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define SZ(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
///const int inf = 1e4
const int MX = 2e5;
const ll inf = 5e14;
vector<vii> tree;
vector<int> subtree_size;
vector<bool> is_removed;
vector<vector<pair<int, ll>>> ancestors;
vector<ll> di;
int get_subtree_size(int u, int p = -1) {
subtree_size[u] = 1;
for (auto & [v, d] : tree[u]) {
if (v == p || is_removed[v]) continue;
subtree_size[u] += get_subtree_size(v, u);
}
return subtree_size[u];
}
int get_centroid(int u, int tree_size, int p = -1) {
for (auto & [v, d] : tree[u]) {
if (v == p || is_removed[v]) continue;
if (subtree_size[v] * 2 > tree_size)
return get_centroid(v, tree_size, u);
}
return u;
}
void get_dists(int u, int centroid, int p, ll dist) {
for (auto & [v, d] : tree[u]) {
if (v == p || is_removed[v]) continue;
get_dists(v, centroid, u, dist + ll(d));
}
ancestors[u].push_back({centroid, dist});
}
void build_centroid_decomp(int u = 0) {
int centroid = get_centroid(u, get_subtree_size(u));
for (auto & [v, d] : tree[centroid]) {
if (is_removed[v]) continue;
get_dists(v, centroid, centroid, ll(d));
}
is_removed[centroid] = 1;
for (auto & [v, d] : tree[centroid]) {
if (is_removed[v]) continue;
// build the centroid decomposition for all child components
build_centroid_decomp(v);
}
}
///t == 1 delete the info
///t == 0 update the info with the distance
void update(int u, bool t){
di[u] = (t) ? inf : 0;
for(auto & [v, d] : ancestors[u]) di[v] = (t) ? inf : min(di[v], d);
}
ll query(int u){
ll ans = di[u];
for(auto & [v, d] : ancestors[u]) ans = min(ans, di[v] + d);
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
is_removed.assign(N, 0);
ancestors.assign(N, vector<pair<int, ll>>());
tree.assign(N, vii());
subtree_size.assign(N, 0);
for0(i, N){
tree[A[i]].pb({B[i], D[i]});
tree[B[i]].pb({A[i], D[i]});
}
build_centroid_decomp(0);
di.assign(N, inf);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
for0(i, S) update(X[i], 0);
for0(i, T) ans = min(ans, query(Y[i]));
for0(i, S) update(X[i], 1);
return ans;
}
