Submit Info #13974

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp wleungBVG AC 300 ms 12.12 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.72 MiB
max_random_00 AC 300 ms 12.12 MiB
max_random_01 AC 292 ms 12.09 MiB
max_random_02 AC 298 ms 12.09 MiB
random_00 AC 188 ms 8.03 MiB
random_01 AC 207 ms 9.26 MiB
random_02 AC 125 ms 3.92 MiB
random_03 AC 95 ms 9.67 MiB
random_04 AC 88 ms 1.80 MiB
small_00 AC 2 ms 0.71 MiB
small_01 AC 2 ms 0.67 MiB
small_02 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;constexpr const char nl='\n',sp=' '; template <class Combine> struct NodeLazyAgg { using Data = typename Combine::Data; using Lazy = typename Combine::Lazy; const static int RANGE_UPDATES = true; const static int RANGE_QUERIES = true; const static int RANGE_REVERSALS = true; const static int HAS_PAR = true; bool rev; int sz; NodeLazyAgg *l, *r, *p; Lazy lz; Data val, sbtr; NodeLazyAgg(const Data &v) : rev(false), sz(1), l(nullptr), r(nullptr), p(nullptr), lz(Combine().ldef), val(v), sbtr(v) {} void update() { sz = 1; sbtr = val; if (l) { sz += l->sz; sbtr = Combine().merge(l->sbtr, sbtr); } if (r) { sz += r->sz; sbtr = Combine().merge(sbtr, r->sbtr); } } void propagate() { if (rev) { swap(l, r); rev = false; if (l) l->reverse(); if (r) r->reverse(); } if (lz != Combine().ldef) { if (l) l->apply(lz); if (r) r->apply(lz); lz = Combine().ldef; } } void apply(const Lazy &v) { val = Combine().applyLazy(val, v); sbtr = Combine().applyLazy(sbtr, Combine().getSegmentVal(v, sz)); lz = Combine().mergeLazy(lz, v); } void reverse() { rev = !rev; Combine().revData(sbtr); } static Data qdef() { return Combine().qdef; } }; template <class _Node, class Container = deque<_Node>> struct Splay { using Node = _Node; Container TR; deque<Node*> deleted; static_assert(Node::HAS_PAR, "Splay Node must have parent pointer"); template <class T> Node *makeNode(const T &v) { if (deleted.empty()) { TR.emplace_back(v); return &TR.back(); } Node *x = deleted.back(); deleted.pop_back(); *x = typename Container::value_type(v); return x; } bool isRoot(Node *x) { return !x->p || (x != x->p->l && x != x->p->r); } void connect(Node *x, Node *p, bool hasCh, bool isL) { if (x) x->p = p; if (hasCh) (isL ? p->l : p->r) = x; } void rotate(Node *x) { Node *p = x->p, *g = p->p; bool isRootP = isRoot(p), isL = x == p->l; connect(isL ? x->r : x->l, p, true, isL); connect(p, x, true, !isL); connect(x, g, !isRootP, !isRootP && p == g->l); p->update(); } void splay(Node *x) { while (!isRoot(x)) { Node *p = x->p, *g = p->p; if (!isRoot(p)) g->propagate(); p->propagate(); x->propagate(); if (!isRoot(p)) rotate((x == p->l) == (p == g->l) ? p : x); rotate(x); } x->propagate(); x->update(); } template <class F> void applyToRange(Node *&root, int i, int j, F f) { int sz = root ? root->sz : 0; if (i <= 0 && sz - 1 <= j) { f(root); if (root) { root->propagate(); root->update(); } } else if (i <= 0) { Node *l = select(root, j + 1)->l; connect(nullptr, root, true, true); root->update(); connect(l, nullptr, false, true); f(l); if (l) { l->propagate(); l->update(); } connect(l, root, true, true); root->update(); } else if (sz - 1 <= j) { Node *r = select(root, i - 1)->r; connect(nullptr, root, true, false); root->update(); connect(r, nullptr, false, false); f(r); if (r) { r->propagate(); r->update(); } connect(r, root, true, false); root->update(); } else { Node *r = select(root, i - 1)->r; connect(nullptr, root, true, false); root->update(); connect(r, nullptr, false, false); Node *l = select(r, j - i + 1)->l; connect(nullptr, r, true, true); r->update(); connect(l, nullptr, false, true); f(l); if (l) { l->propagate(); l->update(); } connect(l, r, true, true); r->update(); connect(r, root, true, false); root->update(); } } Node *select(Node *&root, int k) { Node *last = nullptr; while (root) { (last = root)->propagate(); int t = root->l ? root->l->sz : 0; if (t > k) root = root->l; else if (t < k) { root = root->r; k -= t + 1; } else break; } if (root) splay(root); else if (last) splay(root = last); return root; } int index(Node *&root, Node *x) { root = x; if (!root) return -1; splay(root); return root->l ? root->l->sz : 0; } template <class T, class Comp> pair<int, Node *> getFirst(Node *&root, const T &v, Comp cmp) { pair<int, Node *> ret(0, nullptr); Node *last = nullptr; for (Node *x = root; x;) { (last = x)->propagate(); if (!cmp(x->val, v)) { root = ret.second = x; x = x->l; } else { ret.first += 1 + (x->l ? x->l->sz : 0); x = x->r; } } if (root) splay(root); else if (last) splay(root = last); return ret; } template <class F> Node *buildRec(int l, int r, F &f) { if (l > r) return nullptr; int m = l + (r - l) / 2; Node *left = buildRec(l, m - 1, f); Node *ret = makeNode(f()), *right = buildRec(m + 1, r, f); connect(left, ret, ret, true); connect(right, ret, ret, false); ret->update(); return ret; } template <class F> Node *build(int N, F f) { return buildRec(0, N - 1, f); } void clear(Node *x) { if (!x) return; clear(x->l); deleted.push_back(x); clear(x->r); } }; template <class Node> struct LinkCutTree : public Splay<Node, vector<Node>> { using Tree = Splay<Node, vector<Node>>; using Tree::TR; using Tree::makeNode; using Tree::splay; using Tree::select; using Data = typename Node::Data; using Lazy = typename Node::Lazy; int vert(Node *x) { return x - TR.data(); } Node *access(Node *x) { Node *last = nullptr; for (Node *y = x; y; y = y->p) { splay(y); y->r = last; last = y; } splay(x); return last; } template <const int _ = Node::RANGE_REVERSALS> typename enable_if<_>::type makeRoot(Node *x) { access(x); x->reverse(); } Node *findMin(Node *x) { for (x->propagate(); x->l; (x = x->l)->propagate()); splay(x); return x; } Node *findMax(Node *x) { for (x->propagate(); x->r; (x = x->r)->propagate()); splay(x); return x; } template <const int _ = Node::RANGE_REVERSALS> typename enable_if<_>::type makeRoot(int x) { makeRoot(&TR[x]); } int lca(int x, int y) { if (x == y) return x; access(&TR[x]); Node *ny = access(&TR[y]); return TR[x].p ? vert(ny) : -1; } bool connected(int x, int y) { return lca(x, y) != -1; } template <const int _ = Node::RANGE_REVERSALS> typename enable_if<_>::type link(int x, int y) { makeRoot(y); TR[y].p = &TR[x]; } template <const int _ = Node::RANGE_REVERSALS> typename enable_if<_, bool>::type safeLink(int x, int y) { if (connected(x, y)) return false; link(x, y); return true; } bool linkParent(int par, int ch) { access(&TR[ch]); if (TR[ch].l) return false; TR[ch].p = &TR[par]; return true; } template <const int _ = Node::RANGE_REVERSALS> typename enable_if<_, bool>::type cut(int x, int y) { makeRoot(x); access(&TR[y]); if (&TR[x] != TR[y].l || TR[x].r) return false; TR[y].l->p = nullptr; TR[y].l = nullptr; return true; } bool cutParent(int x) { access(&TR[x]); if (!TR[x].l) return false; TR[x].l->p = nullptr; TR[x].l = nullptr; return true; } int findParent(int x) { access(&TR[x]); return TR[x].l ? vert(findMax(TR[x].l)) : -1; } int findRoot(int x) { access(&TR[x]); return vert(findMin(&TR[x])); } int depth(int x) { access(&TR[x]); return TR[x].l ? TR[x].l->sz : 0; } int kthParent(int x, int k) { int d = depth(x); Node *nx = &TR[x]; return k <= d ? vert(select(nx, d - k)) : -1; } void updateVertex(int x, const Lazy &v) { access(&TR[x]); Node *l = TR[x].l; TR[x].l = nullptr; TR[x].apply(v); TR[x].propagate(); TR[x].update(); TR[x].l = l; } template <const int _ = Node::RANGE_UPDATES> typename enable_if<_>::type updatePathFromRoot(int to, const Lazy &v) { access(&TR[to]); TR[to].apply(v); } template <const int _ = Node::RANGE_UPDATES && Node::RANGE_REVERSALS> typename enable_if<_, bool>::type updatePath( int from, int to, const Lazy &v) { makeRoot(from); access(&TR[to]); if (from != to && !TR[from].p) return false; TR[to].apply(v); return true; } Data queryVertex(int x) { access(&TR[x]); return TR[x].val; } template <const int _ = Node::RANGE_QUERIES> typename enable_if<_, Data>::type queryPathFromRoot(int to) { access(&TR[to]); return TR[to].sbtr; } template <const int _ = Node::RANGE_QUERIES && Node::RANGE_REVERSALS> typename enable_if<_, Data>::type queryPath(int from, int to) { makeRoot(from); access(&TR[to]); return from == to || TR[from].p ? TR[to].sbtr : Node::qdef(); } template <class F> LinkCutTree(int N, F f) { TR.reserve(N); for (int i = 0; i < N; i++) makeNode(f()); } template <class It> LinkCutTree(It st, It en) : LinkCutTree(en - st, [&] { *st++; }) {} }; struct Combine { using Data = ll; using Lazy = ll; const Data qdef = 0; const Lazy ldef = 0; Data merge(const Data &l, const Data &r) const { return l + r; } Data applyLazy(const Data &l, const Lazy &r) const { return l + r; } Lazy getSegmentVal(const Lazy &v, int k) const { return v * k; } Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return l + r; } void revData(Data &v) const {} }; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; LinkCutTree<NodeLazyAgg<Combine>> LCT(N, [&] { ll a; cin >> a; return a; }); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; LCT.link(a, b); } for (int i = 0; i < Q; i++) { int t; cin >> t; if (t == 0) { int a, b, c, d; cin >> a >> b >> c >> d; assert(LCT.cut(a, b)); LCT.link(c, d); } else if (t == 1) { int p; ll x; cin >> p >> x; LCT.updateVertex(p, x); } else { int u, v; cin >> u >> v; cout << LCT.queryPath(u, v) << nl; } } return 0; }