Do use segment treeだけどHL分解は怖いしやり方がよく分からないのでSegment Treeは使わずLink-Cut Treeを使用。
めちゃ雑に書いたけど想像の10倍ぐらい速かった。いつかSplay木のポテンシャル云々を読んでおこう…
平衡二分木の子が左右入れ替わっても値が入れ替わらないもの(sum, maxとか)しか扱ってこなかったためバグった、良い知見。
平行二分木の汎用性の高さには本当に驚かされる
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <queue> #include <set> #include <tuple> #include <cassert> using namespace std; typedef long long ll; typedef pair<int, int> P; struct LCTree { typedef int D; static const int INF = 1LL<<25; struct Node; typedef Node* NP; static Node last_d; static NP last; struct Node { NP p, l, r; int sz; int v, sm, lz; int lsm, rsm, ma, mv; bool rev; Node(D v) :p(NULL), l(last), r(last), sz(1), v(v), sm(v), lz(INF), rev(false), lsm(max(v, 0)), rsm(max(v, 0)), ma(max(v, 0)), mv(v) {} Node(NP l, NP r) : l(l), r(r), sz(0), mv(-INF) {} inline int pos() { if (p && p->l == this) return -1; if (p && p->r == this) return 1; return 0; } void rot() { NP q = p, qq = q->p; int qp = q->pos(); if (q->l == this) { q->l = r; r->p = q; r = q; q->p = this; } else { q->r = l; l->p = q; l = q; q->p = this; } q->update(); update(); p = qq; if (!qp) return; if (qp == -1) { qq->l = this; } else { qq->r = this; } qq->update(); } void splay() { supush(); while (pos()) { int u = pos()*p->pos(); if (!u) { rot(); } else if (u == 1) { p->rot(); rot(); } else { rot(); rot(); } } } void expose() { NP u = this; while (u) { u->splay(); u = u->p; } u = this; while (u->p) { u->p->r = u; u = u->p; u->update(); } splay(); } void push() { if (rev) { swap(l, r); if (l->sz) { l->rev ^= true; swap(l->lsm, l->rsm); } if (r->sz) { r->rev ^= true; swap(r->lsm, r->rsm); } rev = false; } if (lz != INF) { if (l->sz) { l->updata(lz); } if (r->sz) { r->updata(lz); } lz = INF; } } void supush() { if (pos()) { p->supush(); } push(); } void updata(D d) { v = d; sm = sz*d; lz = d; lsm = rsm = ma = max(0, sm); mv = d; } NP update() { if (this == last) return this; sz = 1+l->sz+r->sz; sm = v + l->sm + r->sm; lsm = max(l->lsm, l->sm+v+r->lsm); rsm = max(r->rsm, r->sm+v+l->rsm); ma = max(l->ma, r->ma); ma = max(ma, l->rsm+v+r->lsm); mv = max(l->mv, r->mv); mv = max(mv, v); return this; } } *n; LCTree() : n(last) {} LCTree(NP n) : n(n) {} LCTree(D d) : n(new Node(d)) {} int sz() { return n->sz; } void event() { n->expose(); n->r = last; n->rev = true; swap(n->lsm, n->rsm); } void link(LCTree r) { n->expose(); r.n->expose(); assert(n->l == last); n->p = r.n; } void set(int x) { n->expose(); n->r = last; n->update(); n->updata(x); } int get() { n->expose(); n->r = last; n->update(); if (n->mv < 0) return n->mv; return n->ma; } }; LCTree::Node LCTree::last_d = LCTree::Node((NP)NULL, NULL); LCTree::NP LCTree::last = &last_d; const int MN = 201000; LCTree tr[MN]; vector<int> g[MN]; int root[MN]; int main() { int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { int w; scanf("%d", &w); tr[i] = LCTree(w); } for (int i = 0; i < n-1; i++) { int s, e; scanf("%d %d", &s, &e); s--; e--; g[s].push_back(e); g[e].push_back(s); } queue<P> qu; qu.push(P(0, -1)); while (!qu.empty()) { int a, b; tie(a, b) = qu.front(); qu.pop(); root[a] = b; for (int d: g[a]) { if (d == b) continue; qu.push(P(d, a)); } } for (int i = 1; i < n; i++) { tr[i].link(tr[root[i]]); } for (int i = 0; i < q; i++) { int t, a, b, c; scanf("%d %d %d %d", &t, &a, &b, &c); a--; b--; if (t == 1) { tr[a].event(); tr[b].set(c); } else { tr[a].event(); printf("%d\n", tr[b].get()); } } }