Submit Info #5535

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp Haar AC 545 ms 15.23 MiB

ケース詳細
Name Status Time Memory
example_00 AC 0 ms 0.67 MiB
max_random_00 AC 545 ms 15.18 MiB
max_random_01 AC 530 ms 15.23 MiB
max_random_02 AC 540 ms 15.16 MiB
random_00 AC 348 ms 9.99 MiB
random_01 AC 382 ms 11.55 MiB
random_02 AC 212 ms 4.79 MiB
random_03 AC 220 ms 12.29 MiB
random_04 AC 139 ms 2.05 MiB
small_00 AC 2 ms 0.72 MiB
small_01 AC 3 ms 0.67 MiB
small_02 AC 2 ms 0.67 MiB

#include <bits/stdc++.h> template <typename Monoid> struct LinkCutNode{ using value_type = typename Monoid::value_type; using node = LinkCutNode; int subsize; node *left, *right, *parent; bool rev; value_type value, result; LinkCutNode(){ subsize = 1; left = right = parent = nullptr; rev = false; value = result = Monoid::id(); } bool is_root() const { return !parent or (parent->left != this and parent->right != this); } void update_node_status(){ subsize = 1; result = value; if(left){ left->push_down(); subsize += left->subsize; result = Monoid::op(result, left->result); } if(right){ right->push_down(); subsize += right->subsize; result = Monoid::op(result, right->result); } } void push_down(){ if(rev){ std::swap(left, right); if(left) left->rev ^= true; if(right) right->rev ^= true; rev = false; } } void rot(int dir_right){ node *p = parent, *g = p->parent; if(dir_right){ if((p->left = right)) right->parent = p; right = p; p->parent = this; }else{ if((p->right = left)) left->parent = p; left = p; p->parent = this; } p->update_node_status(); update_node_status(); parent = g; if(!g) return; if(g->left == p) g->left = this; if(g->right == p) g->right = this; g->update_node_status(); } void splay(){ while(not is_root()){ node *p = parent, *gp = p->parent; if(p->is_root()){ p->push_down(); push_down(); rot(this == p->left); }else{ gp->push_down(); p->push_down(); push_down(); bool flag = this == p->left; if((this == p->left) == (p == gp->left)){ p->rot(flag); rot(flag); }else{ rot(flag); rot(!flag); } } } push_down(); } static void expose(node *u){ node* rp = nullptr; for(node* p = u; p; p = p->parent){ p->splay(); p->right = rp; p->update_node_status(); rp = p; } u->splay(); } static void link(node *u, node *v){ evert(u); u->parent = v; } static void cut(node *u){ expose(u); u->left->parent = nullptr; u->left = nullptr; u->update_node_status(); } static void cut(node *u, node *v){ expose(u); expose(v); if(u->is_root()) u->parent = nullptr; else{ v->left->parent = nullptr; v->left = nullptr; v->update_node_status(); } } static void evert(node *u){ expose(u); u->rev ^= true; u->push_down(); } }; template <typename Monoid> class LinkCutTree{ public: using value_type = typename Monoid::value_type; using node = LinkCutNode<Monoid>; int N; std::vector<node*> nodes; LinkCutTree(int N): N(N), nodes(N){ for(int i = 0; i < N; ++i){ nodes[i] = new node(); } } void expose(int k){ node::expose(nodes[k]); } void cut(int i, int j){ node::cut(nodes[i], nodes[j]); } void link(int c, int p){ node::link(nodes[c], nodes[p]); } void evert(int k){ node::evert(nodes[k]); } void update(int k, value_type x){ node::evert(nodes[k]); nodes[k]->value = x; nodes[k]->push_down(); } value_type at(int k){ return nodes[k]->value; } value_type get(int u, int v){ node::evert(nodes[u]); node::expose(nodes[v]); return nodes[v]->result; } }; template <typename T> struct SumMonoid{ using value_type = T; constexpr inline static value_type id(){return 0;} constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;} }; using M = SumMonoid<int64_t>; int get_int(){ int ret; std::cin >> ret; return ret; } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); int N, Q; std::cin >> N >> Q; LinkCutTree<M> lct(N); for(int i = 0; i < N; ++i){ int64_t a; std::cin >> a; lct.update(i, a); } for(int i = 0; i < N-1; ++i){ int u, v; std::cin >> u >> v; lct.link(u, v); } while(Q--){ switch(get_int()){ case 0: { int u, v, w, x; std::cin >> u >> v >> w >> x; lct.cut(u, v); lct.link(w, x); break; } case 1: { int p, x; std::cin >> p >> x; lct.update(p, lct.at(p) + x); break; } case 2: { int u, v; std::cin >> u >> v; auto ans = lct.get(u, v); std::cout << ans << std::endl; break; } } } return 0; }