#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? */