Submit Info #60433

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum cpp14 etyu39 AC 1591 ms 69.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
max_random_00 AC 1591 ms 69.46 MiB
max_random_01 AC 1544 ms 69.57 MiB
max_random_02 AC 1554 ms 69.57 MiB
max_random_03 AC 1544 ms 69.62 MiB
max_random_04 AC 1557 ms 69.57 MiB
random_00 AC 994 ms 44.70 MiB
random_01 AC 1123 ms 52.57 MiB
random_02 AC 588 ms 19.07 MiB
random_03 AC 470 ms 57.44 MiB
random_04 AC 346 ms 5.95 MiB
small_00 AC 2 ms 0.71 MiB
small_01 AC 1 ms 0.45 MiB
small_02 AC 1 ms 0.45 MiB
small_03 AC 1 ms 0.45 MiB
small_04 AC 3 ms 0.57 MiB

#include <iostream> #include <algorithm> #include <assert.h> using namespace std; struct node { node* p = nullptr, * l = nullptr, * r = nullptr, * fl = nullptr, * fr = nullptr; int compressedVertex = 0, endL = 0, endR = 0; long long v = 0, s = 0, lz = 0; int sz = 0; bool isVertex = false, isCompress = false, needRectify = false; node(node* p, node* l, node* r) : p(p), l(l), r(r) { l->p = this; r->p = this; }; node(int x, int y) : endL(x), endR(y) {}; node() {}; }; node* handle[400009]; int degree[400009]; bool isRoot(node* x) { return (!x->p || (x->p->isCompress != x->isCompress || x->p->fl == x || x->p->fr == x)); } void update(node* x) { assert(!x->lz); x->s = x->v; x->sz = (int)x->isVertex; if (x->l && x->r) { x->sz += x->l->sz; x->s += x->l->s; x->sz += x->r->sz; x->s += x->r->s; x->endL = x->l->endL ^ x->l->endR ^ x->compressedVertex; x->endR = x->r->endL ^ x->r->endR ^ x->compressedVertex; } if (x->fl) { x->sz += x->fl->sz; x->s += x->fl->s; } if (x->fr) { x->sz += x->fr->sz; x->s += x->fr->s; } if (x->isCompress && isRoot(x)) { if (degree[x->endL] == 1) handle[x->endL] = x; if (degree[x->endR] == 1) handle[x->endR] = x; } } void lazy(node* x) { if (x->lz) { if (x->l) { x->l->lz += x->lz; if (x->l->isVertex) x->l->v += x->lz; x->l->s += x->lz * x->l->sz; } if (x->r) { x->r->lz += x->lz; if (x->r->isVertex) x->r->v += x->lz; x->r->s += x->lz * x->r->sz; } if (x->fl) { x->fl->lz += x->lz; if (x->fl->isVertex) x->fl->v += x->lz; x->fl->s += x->lz * x->fl->sz; } if (x->fr) { x->fr->lz += x->lz; if (x->fr->isVertex) x->fr->v += x->lz; x->fr->s += x->lz * x->fr->sz; } x->lz = 0; } } node* findCompressNode(node* x) { assert(x->p); x = x->p; while (!x->isCompress) x = x->p; return x; } void updateChild(node* p, node* a, node* b) { p->l = a; p->r = b; if (a) a->p = p; if (b) b->p = p; } void updateFosterChild(node* p, node* a, node* b) { p->fl = a; p->fr = b; if (a) a->p = p; if (b) b->p = p; } void swapChild(node* x) { swap(x->l, x->r); swap(x->fl, x->fr); swap(x->endL, x->endR); } void rectifyNode(node* x) { assert(x); if (!x->isCompress) return; if (!x->l) return; if (isRoot(x)) { if (handle[x->endL]->compressedVertex == x->endL) swapChild(x); } else { if (x->p->l == x) { if (x->endR != x->p->compressedVertex) swapChild(x); } else if (x->p->r == x) { if (x->endL != x->p->compressedVertex) swapChild(x); } else assert(false); } } void rectify(node* x) { assert(x); while (true) { x->needRectify = true; if (x->l && x->r) { x->endL = x->l->endL ^ x->l->endR ^ x->compressedVertex; x->endR = x->r->endL ^ x->r->endR ^ x->compressedVertex; } if (!x->p) break; x = x->p; } while (true) { rectifyNode(x); lazy(x); x->needRectify = false; if (x->l && x->l->needRectify) x = x->l; else if (x->r && x->r->needRectify) x = x->r; else if (x->fl && x->fl->needRectify) x = x->fl; else if (x->fr && x->fr->needRectify) x = x->fr; else break; } } void rotate(node* x) { assert(x); if (isRoot(x)) return; node* p = x->p; if (p->l == x) { if (x->r) x->r->p = p; p->l = x->r; x->r = p; } else { if (x->l) x->l->p = p; p->r = x->l; x->l = p; } x->p = p->p; p->p = x; if (x->p) { if (x->p->l == p) x->p->l = x; else if (x->p->r == p) x->p->r = x; else if (x->p->fl == p) x->p->fl = x; else if (x->p->fr == p) x->p->fr = x; else assert(false); } update(p); update(x); } void splay(node* x, node* guard = nullptr) { assert(x); update(x); if (x == guard) return; while (!isRoot(x) && x->p != guard) { if (!isRoot(x->p) && x->p->p != guard) { node* p = x->p, * g = p->p; if ((p->l == x) == (g->l == p)) rotate(p); else rotate(x); } rotate(x); } update(x); } void spliceStep(node* x, node* guard = nullptr) { assert(x); assert(x->isCompress); assert(x->p && isRoot(x)); node* p0 = x->p, * p1 = p0->p, * p2 = (p1 ? p1->p : nullptr); if (p1 && !p0->isCompress && !p1->isCompress && (p1->l == p0) == (p0->l == x)) { rotate(p0); p0 = x->p; p1 = p0->p; p2 = p1->p; } node* p = findCompressNode(x); splay(p, guard); if (!isRoot(p) && p->p->r == p) { swapChild(p->p); swapChild(p); } node* y = p->l; p->l = x; x->p = p; if (p0->isCompress) { if (p0->fl == x) { node* A = p0->fr; if (A) updateFosterChild(p0, nullptr, new node(p0, y, A)); else updateFosterChild(p0, nullptr, y); } else { node* A = p0->fl; if (A) updateFosterChild(p0, new node(p0, A, y), nullptr); else updateFosterChild(p0, y, nullptr); } } else if (p1->isCompress) { if (p1->fl == p0) { node* B = p1->fr; if (p0->l == x) { node* A = p0->r; updateFosterChild(p1, nullptr, p0); if (B) updateChild(p0, A, new node(p0, y, B)); else updateChild(p0, A, y); } else { node* A = p0->l; if (B) { updateFosterChild(p1, A, p0); updateChild(p0, y, B); } else { delete p0; updateFosterChild(p1, A, y); } } } else { node* B = p1->fl; if (p0->r == x) { node* A = p0->l; updateFosterChild(p1, p0, nullptr); if (B) updateChild(p0, new node(p0, B, y), A); else updateChild(p0, y, A); } else { node* A = p0->r; if (B) { updateFosterChild(p1, p0, A); updateChild(p0, B, y); } else { delete p0; updateFosterChild(p1, y, A); } } } } else { if (p2->fl == p1) { node* A = nullptr, * B = nullptr, * C = p2->fr; if (p1->l == p0) { A = p0->l; B = p1->r; } else { A = p1->l; B = p0->r; } updateFosterChild(p2, A, p1); if (C) { updateChild(p1, p0, C); updateChild(p0, B, y); } else { delete p0; updateChild(p1, B, y); } } else { node* A = nullptr, * B = nullptr, * C = p2->fl; if (p1->l == p0) { A = p1->r; B = p0->l; } else { A = p0->r; B = p1->l; } updateFosterChild(p2, p1, A); if (C) { updateChild(p1, C, p0); updateChild(p0, y, B); } else { delete p0; updateChild(p1, y, B); } } } lazy(y); while (true) { update(y); if (y == p) break; y = y->p; } } node* splice(int vx, node* guard = nullptr) { node* x = handle[vx]; assert(x); assert(x->isCompress); if (x == guard) return x; rectify(x); update(x); if (!x->l) { if (!x->p) return x; node* p = x->p; assert(p); if (!p->isCompress) { splay(p); splay(x->p, p); } spliceStep(x, guard); if (x->p == guard) return x; x = x->p; } splay(x, guard); while (x->p && (!guard || guard->fl == x || guard->fr == x || x->p != guard)) { node* p = x->p; if (!p->isCompress) { splay(p); splay(x->p, p); } spliceStep(x, guard); splay(x, guard); } update(x); if (guard) update(guard); return x; } node* expose(int vx, int vy) { assert(vx != vy); assert(degree[vx] > 0 && degree[vy] > 0); if (degree[vx] == 1 && degree[vy] > 1) swap(vx, vy); node* x = splice(vx); if (degree[vx] == 1) { assert(degree[vy] == 1); if (x->endL == vx) swapChild(x); node* y = handle[vy]; if (x == y) { return x; } y = splice(vy); return y; } else { node* y = handle[vy]; if (x == y) { assert(degree[vy] == 1); if (x->endL == vy) swapChild(x); return x->r; } else { y = splice(vy, x); assert(x != y); assert(x->l == y || x->r == y); if (x->l == y) swapChild(x); if (degree[vy] == 1) return y; else { if (y->endL == vx) swapChild(y); return y->r; } } } } void recoverRightNode(node* x) { assert(x); assert(!x->p); lazy(x); if (x->r) return; if (x->fr) { node* y = x->fr; while (y->r && !y->isCompress) { lazy(y); y = y->r; } node* p = y->p; x->r = y; y->p = x; if (p == x) { x->fr = nullptr; } else { node* g = p->p; if (g == x) g->fr = p->l; else g->r = p->l; p->l->p = g; update(g); delete p; if (g != x) splay(g); } update(x); } else if (x->fl) { node* y = x->fl; while (y->l && !y->isCompress) { lazy(y); y = y->l; } node* p = y->p; x->r = y; y->p = x; if (p == x) { x->fl = nullptr; } else { node* g = p->p; if (g == x) g->fl = p->r; else g->l = p->r; p->r->p = g; update(g); delete p; if (g != x) splay(g); } update(x); } else { x->l->p = nullptr; lazy(x->l); update(x->l); delete x; } } void addRightNode(int vx, node* t) { node* x = splice(vx); assert(x); assert(t); lazy(x); node* r = x->r; if (x->fr) { node* y = x->fr; while (y->r && !y->isCompress) { lazy(y); y = y->r; } if (y->p == x) x->fr = new node(x, y, x->r); else { node* p = y->p; p->r = new node(p, y, x->r); } splay(y->p); } else x->fr = x->r; x->r = t; t->p = x; lazy(r); update(r); update(x); } void addEndNode(int vx, node* t) { node* x = splice(vx); assert(x); assert(t); lazy(x); if (x->r) { while (x->r) { if (x->endL == vx) swapChild(x); lazy(x); x = x->r; } x = new node(x->p, x, t); x->p->r = x; } else { x = new node(nullptr, x, t); } x->isCompress = true; x->compressedVertex = vx; handle[vx] = x; splice(vx); } void cut(int vx, int vy) { if (degree[vx] < degree[vy]) swap(vx, vy); node* x = expose(vx, vy); degree[vx]--; degree[vy]--; if (degree[vx] == 0 && degree[vy] == 0) { delete x; } else if (degree[vx] > 0) { node* p = x->p; if (!p->p) { lazy(p); p->r = nullptr; delete x; recoverRightNode(p); } else { node* g = p->p; lazy(g); lazy(p); g->r = nullptr; p->r = nullptr; p->p = nullptr; delete x; recoverRightNode(g); recoverRightNode(p); } }; if (!degree[vx]) handle[vx] = nullptr; if (!degree[vy]) handle[vy] = nullptr; } void link(int vx, int vy) { if (degree[vx] < degree[vy]) swap(vx, vy); node* t = new node(vx, vy); t->isCompress = true; degree[vx]++; degree[vy]++; update(t); if (degree[vx] == 1 && degree[vy] == 1) { handle[vx] = t; handle[vy] = t; } else if (degree[vx] == 2 && degree[vy] == 1) { addEndNode(vx, t); } else if (degree[vx] == 2 && degree[vy] == 2) { addEndNode(vy, t); addEndNode(vx, handle[vy]); } else if (degree[vx] > 2 && degree[vy] == 1) { addRightNode(vx, t); } else if (degree[vx] > 2 && degree[vy] == 2) { addEndNode(vy, t); addRightNode(vx, handle[vy]); } else if (degree[vx] > 2 && degree[vy] > 2) { addRightNode(vy, t); addRightNode(vx, handle[vy]); } else assert(false); } void treeAddQuery(int vx, int vp, int w) { if (degree[vx] == 1) return; expose(vx, vp); node* x = handle[vx]; lazy(x); x->l->lz += w; if (x->l->isVertex) x->l->v += w; x->l->s += 1LL * x->l->sz * w; if (x->fl) { x->fl->lz += w; if (x->fl->isVertex) x->fl->v += w; x->fl->s += 1LL * x->fl->sz * w; } if (x->fr) { x->fr->lz += w; if (x->fr->isVertex) x->fr->v += w; x->fr->s += 1LL * x->fr->sz * w; } x->v += w; update(x); } long long treeSumQuery(int vx, int vp) { if (degree[vx] == 1) return 0; expose(vx, vp); node* x = handle[vx]; lazy(x); return x->s - x->r->s; } void updateAll(node* x) { if (x->l) updateAll(x->l); if (x->r) updateAll(x->r); if (x->fl) updateAll(x->fl); if (x->fr) updateAll(x->fr); update(x); } void updateAll(int n) { for (int i = 1; i <= n; i++) { node* x = handle[i]; if (!degree[i]) continue; else if (degree[i] == 1) { assert(x); if (!x->p && !x->r && x->endL == i) updateAll(x); } else if (!x->p) updateAll(x); } } void printTree(node* n, int d) { for (int i = 0; i < d; i++) cout << " "; if (n->isCompress) cout << n->compressedVertex << ", " << n->endL << "-" << n->endR << " " << n->v << " "; else cout << "R, "; cout << '\n'; if (!n->l) return; if (n->fl) printTree(n->fl, d + 1); else if (n->isCompress) { for (int i = 0; i < d + 1; i++) cout << " "; cout << "FL\n"; } if (n->l) printTree(n->l, d + 1); if (n->fr) printTree(n->fr, d + 1); else if (n->isCompress) { for (int i = 0; i < d + 1; i++) cout << " "; cout << "FR\n"; } if (n->r) printTree(n->r, d + 1); } void printTree(int n) { cout << "-------->\n"; for (int i = 1; i <= n; i++) { node* x = handle[i]; if (!degree[i]) continue; else if (degree[i] == 1) { assert(x); if (!x->p && !x->r && x->endL == i) { printTree(x, 0); cout << '\n' << '\n'; } } else if (!x->p) { printTree(x, 0); cout << '\n' << '\n'; } } for (int i = 1; i <= n; i++) { if (!handle[i]) cout << "X "; else cout << "(" << handle[i]->endL << ", " << handle[i]->endR << ") "; } cout << '\n'; cout << "<---------\n"; } int va[200009]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> va[i]; link(i, n + i); } for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a++; b++; link(a, b); } for (int i = 1; i <= n; i++) { node* x = handle[i]; x->isVertex = true; x->v = va[i]; } updateAll(2 * n); for (int i = 0; i < q; i++) { int t; cin >> t; if (t == 0) { int a0, b0, a1, b1; cin >> a0 >> b0 >> a1 >> b1; a0++; b0++; a1++; b1++; bool v0 = false, v1 = false; if (degree[a0] == 2) { link(a0, 2 * n + 1); v0 = true; } if (degree[b0] == 2) { link(b0, 2 * n + 2); v1 = true; } cut(a0, b0); link(a1, b1); if (v0) cut(a0, 2 * n + 1); if (v1) cut(b0, 2 * n + 2); } else if (t == 1) { int a, p, w; cin >> a >> p >> w; a++; p++; treeAddQuery(a, p, w); } else { int a, p; cin >> a >> p; a++; p++; cout << treeSumQuery(a, p) << '\n'; } } return 0; }