#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));
const int mod = 1e9 + 7;
const ll inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int NN = 5e5 + 5;
const int LG = 21;
ll sz[NN], depth[NN], par[NN], dis[LG][NN];
bool visited[NN];
vector <pii> adj[NN];
ll dfssz(ll u, ll p){
sz[u] = 0;
for (auto [w, v] : adj[u]) {
if (v == p || visited[v]) continue;
sz[u] += dfssz(v, u);
}
return ++sz[u];
}
ll centroid(ll u, ll p, ll szz){
for (auto [w, v] : adj[u]) {
if (visited[v] || v == p) continue;
if (2 * sz[v] > szz) return centroid(v, u, szz);
}
return u;
}
void filldist(int u, int p, int d){
for (auto [w, v] : adj[u]) {
if (v == p || visited[v]) continue;
dis[d][v] = dis[d][u] + w;
filldist(v, u, d);
}
}
void decompose(int u, int p){
int c = centroid(u, u, dfssz(u, u));
visited[c] = true;
if (p != -1) par[c] = p;
if (p != -1) depth[c] = depth[p] + 1;
filldist(c, c, depth[c]);
for (auto [w, v] : adj[c]) {
if (visited[v]) continue;
decompose(v, c);
}
}
ll mn[NN];
set <ll> changed;
void Init(int n, int u[], int v[], int w[]) {
memset(par, -1, sizeof par);
for (int i = 0; i < n; i++) mn[i] = inf;
for (int i = 0; i < n - 1; i++) {
adj[u[i]].emb(w[i], v[i]);
adj[v[i]].emb(w[i], u[i]);
}
decompose(0, -1);
}
void update(int u){
int v = u;
while (v != -1) {
changed.emplace(v);
mn[v] = min(mn[v], dis[depth[v]][u]);
v = par[v];
}
}
ll query(ll u){
ll ans = mn[u];
ll v = u;
while (v != -1) {
ans = min(ans, mn[v] + dis[depth[v]][u]);
v = par[v];
}
return ans;
}
long long Query(int xn, int x[], int yn, int y[]) {
changed.clear();
for (int i = 0; i < xn; i++) update(x[i]);
ll ans = inf;
for (int i = 0; i < yn; i++) ans = min(ans, query(y[i]));
for (auto e : changed) mn[e] = inf;
return ans;
}
/*
similar to Xenia and Tree problem (Centroid Tree)
(but in this case, we also remove red nodes)
-> doable by recording nodes that were edited, then fix there
... jote ta?
*/
