Hướng dẫn giải của DeMenQuery02
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <bits/stdc++.h> #define ll long long //#define int long long // Judges with GCC >= 12 only needs Ofast #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize") // MLE optimization #pragma GCC optimize("conserve-stack") // Old judges #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2") // New judges. Test with assert(__builtin_cpu_supports("avx2")); #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native") // Atcoder #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma") using namespace std; const int N = 3e5 + 5; int n, q; vector <int> adj[N]; int h[N], id[N], head[N], par[N], s[N], pos[N], in[N], out[N], cnt, chain; namespace seg2n { ll st[2*N], d[N]; int h, a[N]; inline void apply(int pos, ll val) { st[pos]+=val; if (pos<=n) d[pos]+=val; } inline void down(int pos) { for (int s=h; s; s--) { int i = pos>>s; if (d[i]!=0) { apply(i<<1, d[i]); apply(i<<1|1, d[i]); d[i] = 0; } } } inline void build(int pos) { while (pos>>=1) st[pos] = max(st[pos<<1], st[pos<<1|1]) + d[pos]; } inline void inc(int l, int r, ll val) { int l0 = l, r0 = r; for (l+=n, r+=n+1, down(l), down(r); l<r; l>>=1, r>>=1) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } build(l0+n); build(r0+n); } inline ll qry(int l, int r) { if (l==0) return 0; ll ans = -1e18; for (l+=n, r+=n+1, down(l), down(r); l<r; l>>=1, r>>=1) { if (l&1) ans = max(ans, st[l++]); if (r&1) ans = max(ans, st[--r]); } return ans; } inline void reset() { st[n<<1|1] = -1e18; for (int i=1; i<=n; i++) a[i] = 0, st[n+i] = a[i], st[n+i]+=st[n+i-1]; for (int i=n; i>=1; i--) st[i] = max(st[i<<1], st[i<<1|1]); h = log2(n); } } void dfs(int u, int p, int dep) { h[u] = dep; par[u] = p; s[u] = 1; for (int v : adj[u]) if (v != p) { dfs(v, u, dep + 1); s[u] += s[v]; } } void hld(int u, int p) { if (head[chain] == 0) head[chain] = u; id[u] = chain; pos[u] = in[u] = ++cnt; int x = -1; for (int v : adj[u]) if (v != p) if (x == -1 || s[x] < s[v]) x = v; if (x != -1) hld(x, u); for (int v : adj[u]) if (v != p && v != x) { chain++; hld(v, u); } out[u] = cnt; } inline void upd(int u, int v, int val) { while (id[u] != id[v]) { if (h[head[id[u]]] > h[head[id[v]]]) swap(u, v); // add(1, 1, n, pos[head[id[v]]], pos[v], val); seg2n::inc(pos[head[id[v]]], pos[v], val); v = par[head[id[v]]]; } if (h[u] > h[v]) swap(u, v); // add(1, 1, n, pos[u], pos[v], val); seg2n::inc(pos[u], pos[v], val); } inline ll qry(int u, int v) { ll ans = 0; while (id[u] != id[v]) { if (h[head[id[u]]] > h[head[id[v]]]) swap(u, v); // ans = max(ans, get(1, 1, n, pos[head[id[v]]], pos[v])); ans = max(ans, seg2n::qry(pos[head[id[v]]], pos[v])); v = par[head[id[v]]]; } if (h[u] > h[v]) swap(u, v); // ans = max(ans, get(1, 1, n, pos[u], pos[v])); ans = max(ans, seg2n::qry(pos[u], pos[v])); return ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> q; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 1, 0); cnt = 0; chain = 1; hld(1, 1); seg2n::reset(); for (int i = 1; i <= q; i++) { int type; cin >> type; if (type == 1) { int u, v, val; cin >> u >> v >> val; /** cập nhật các đỉnh i thuộc đường đi từ u đến v: a[i] += val **/ upd(u, v, val); } else if (type == 2) { int u, val; cin >> u >> val; /** cập nhật các đỉnh i thuộc cây con của u: a[i] += val **/ // add(1, 1, n, in[u], out[u], val); seg2n::inc(in[u], out[u], val); } else if (type == 3) { int u, v; cin >> u >> v; /** truy vấn max(a[i]) các đỉnh i thuộc đường đi từ u đến v **/ ll ans = qry(u, v); cout << ans << '\n'; } else if (type == 4) { int u, v; cin >> u; /** truy vấn max(a[i]) các đỉnh i thuộc cây con của u **/ // ll ans = get(1, 1, n, in[u], out[u]); ll ans = seg2n::qry(in[u], out[u]); cout << ans << '\n'; } } }
Bình luận