Untitled
unknown
plain_text
a year ago
3.5 kB
4
Indexable
#include<bits/stdc++.h> using ll = long long; using namespace std; void File() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("errors.txt", "w", stderr); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } struct SegTree { const long long ID{}; static long long cmb(long long a, long long b) { return max(a, b); } void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); } int n{}; vector<long long> seg; void init(int _n) { for (n = 1; n <= _n;) n *= 2; seg.assign(2 * n, ID); } void upd(int p, long long val) { seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); } long long query(int l, int r) { long long ra = ID, rb = ID; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) ra = cmb(ra, seg[l++]); if (r & 1) rb = cmb(seg[--r], rb); } return cmb(ra, rb); } }; struct HLD { vector<int> par, head, heavy, pos, depth; int timer{}; SegTree seg; explicit HLD(const vector<vector<int>> &adj, vector<int> &v) { int n = (int) adj.size(); par.assign(n, 0), head.assign(n, 0); heavy.assign(n, -1), pos.assign(n, 0); depth.assign(n, 0), timer = 0; dfs(0, adj); decomposition(0, 0, adj); seg.init(n); for (int i = 0; i < n; ++i) seg.upd(pos[i], v[i]); } int dfs(int u, const vector<vector<int>> &adj) { int sz = 1, MX = 0; for (auto &v: adj[u]) { if (v == par[u]) continue; par[v] = u, depth[v] = depth[u] + 1; int s = dfs(v, adj); if (s > MX) MX = s, heavy[u] = v; } return sz; } void decomposition(int u, int h, const vector<vector<int>> &adj) { pos[u] = timer++, head[u] = h; if (~heavy[u]) decomposition(heavy[u], h, adj); for (auto &v: adj[u]) if (v != par[u] && v != heavy[u]) decomposition(v, v, adj); } static long long calc(long long x, long long y) { return max(x, y); } long long getDS(int u, int v) { return seg.query(pos[u], pos[v]); } long long query(int u, int v) { long long res = 0; for (; head[u] != head[v]; v = par[head[v]]) { if (depth[head[u]] > depth[head[v]]) swap(u, v); res = calc(res, getDS(head[v], v)); } if (depth[u] > depth[v]) swap(u, v); res = calc(res, getDS(u, v)); return res; } }; int main() { File(); int n, q; cin >> n >> q; vector<int> val(n); vector<vector<int>> adj(n); for (int i = 0; i < n; ++i) cin >> val[i]; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); adj[v].push_back(u); } HLD hld(adj, val); for (int i = 0; i < q; ++i) { int t; cin >> t; if(t == 1) { ll u, v; cin >> u >> v; hld.seg.upd(hld.pos[u - 1], v); } else { int u, v; cin >> u >> v; cout << hld.query(u - 1, v - 1) << " "; } } return 0; }
Editor is loading...
Leave a Comment