Submit Info #3211

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp QCFium AC 432 ms 14.43 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.68 MiB
max_random_00 AC 432 ms 14.42 MiB
max_random_01 AC 423 ms 14.43 MiB
max_random_02 AC 430 ms 14.39 MiB
random_00 AC 272 ms 9.55 MiB
random_01 AC 305 ms 11.05 MiB
random_02 AC 162 ms 4.55 MiB
random_03 AC 185 ms 11.55 MiB
random_04 AC 107 ms 2.05 MiB
small_00 AC 3 ms 0.74 MiB
small_01 AC 2 ms 0.70 MiB
small_02 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } struct LCT { #define l ch[0] #define r ch[1] struct Node { Node *p; Node *ch[2]; bool rev; int64_t sum; int64_t val; int size; void fetch() { if (l != LCT::NONE) l->flush(); if (r != LCT::NONE) r->flush(); sum = val + l->sum + r->sum; size = 1 + l->size + r->size; } void flush() { if (rev) { l->rev ^= 1; r->rev ^= 1; std::swap(l, r); rev = false; } } bool is_root() { return p == LCT::NONE || (p->l != this && p->r != this); } void rotate(int dir) { Node *new_root = ch[!dir], *par = p; ch[!dir] = new_root->ch[dir]; ch[!dir]->p = this; new_root->ch[dir] = this; p = new_root; fetch(), new_root->fetch(); new_root->p = par; if (par->l == this) par->l = new_root; else if (par->r == this) par->r = new_root; } }; void splay(Node *node) { while (!node->is_root()) { Node *p = node->p; if (p->is_root()) { p->flush(), node->flush(); p->rotate(p->l == node); } else { Node *pp = p->p; pp->flush(), p->flush(), node->flush(); bool flag1 = p->l == node; bool flag2 = pp->l == p; if (flag1 == flag2) pp->rotate(flag2); p->rotate(flag1); if (flag1 != flag2) pp->rotate(flag2); } } node->flush(); } static Node *nodes, *NONE; static int head; LCT () { if (!head) nodes[head++] = {NONE, {NONE, NONE}, false, 0, 0, 0}; } Node *expose(Node *start) { Node *prev = NONE; for (Node *cur = start; cur != NONE; cur = cur->p) { splay(cur); cur->r = prev; cur->fetch(); prev = cur; } splay(start); return prev; } void link(Node *child, Node *parent) { expose(child), expose(parent); parent->r = child; child->p = parent; parent->fetch(); } void cut(Node *child) { expose(child); Node *parent = child->l; parent->p = NONE; child->l = NONE; child->fetch(); } void reroot(Node *node) { expose(node); node->rev ^= 1; node->flush(); } Node *new_node(int val) { return &(nodes[head++] = {NONE, {NONE, NONE}, false, val, val, 1}); } Node *get_root(Node *node) { expose(node); for (; node->flush(), (node->l != NONE); node = node->l); return node; } Node *lca(Node *a, Node *b) { expose(a); return expose(b); } void debug(Node *node, int indent = 0, int dir = 0) { if (node == NONE) return; for (int i = 0; i < indent; i++) fprintf(stderr, " "); if (dir) fprintf(stderr, dir > 0 ? "R " : "L "); fprintf(stderr, "%d : val:%lld sz:%d p:%d rev:%d\n", (int) (node - nodes), (long long) node->val, node->size, (int) (node->p - nodes), node->rev); debug(node->l, indent + 1, -1); debug(node->r, indent + 1, 1); } #undef l #undef r }; LCT::Node *LCT::nodes = (Node *) malloc(sizeof(Node) * 1000000), *LCT::NONE = nodes; int LCT::head = 0; // verify LCT int main() { int n = ri(); int q = ri(); std::vector<int> a(n); for (auto &i : a) i = ri(); LCT tree; LCT::Node *nodes[n]; for (int i = 0; i < n; i++) nodes[i] = tree.new_node(a[i]); for (int i = 0; i + 1 < n; i++) { int x = ri(), y = ri(); tree.reroot(nodes[x]); tree.link(nodes[x], nodes[y]); } for (int i = 0; i < q; i++) { int t = ri(); if (t == 0) { int x = ri(), y = ri(); tree.reroot(nodes[y]); tree.cut(nodes[x]); x = ri(), y = ri(); tree.reroot(nodes[x]); tree.link(nodes[x], nodes[y]); } else if (t == 1) { int p = ri(), x = ri(); tree.expose(nodes[p]); nodes[p]->val += x; } else if (t == 2) { int x = ri(), y = ri(); tree.reroot(nodes[x]); tree.expose(nodes[y]); printf("%lld\n", (long long) nodes[y]->sum); } } return 0; }