Submit Info #4252

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp (anonymous) AC 278 ms 15.95 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.72 MiB
max_random_00 AC 278 ms 15.95 MiB
max_random_01 AC 266 ms 15.92 MiB
max_random_02 AC 269 ms 15.92 MiB
random_00 AC 168 ms 10.42 MiB
random_01 AC 191 ms 12.17 MiB
random_02 AC 109 ms 4.93 MiB
random_03 AC 94 ms 12.91 MiB
random_04 AC 73 ms 2.05 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 2 ms 0.68 MiB

#include <bits/stdc++.h> using namespace std; template <class InfoType, class SumType = InfoType> struct LinkCutTree { struct Node { Node *ch[2], *fa, *pfa; InfoType info; SumType sum; bool rev; enum RelType { LEFT, RIGHT }; template <class ...Args> Node(Args &&...args) : info(forward<Args>(args)...), rev(false), fa(nullptr), pfa(nullptr) { ch[0] = nullptr; ch[1] = nullptr; sum = info; } RelType Relation() const { return this == fa->ch[0] ? LEFT : RIGHT; } void Push() { if (!rev) return; swap(ch[0], ch[1]); if (ch[0]) ch[0]->rev ^= true; if (ch[1]) ch[1]->rev ^= true; rev = false; } void Pull() { sum = info; if (ch[0]) sum += ch[0]->sum; if (ch[1]) sum += ch[1]->sum; } void Rotate() { if (fa->fa) fa->fa->Push(); fa->Push(); Push(); swap(pfa, fa->pfa); RelType rel = Relation(); Node *t = fa; if (t->fa) t->fa->ch[t->Relation()] = this; fa = t->fa; t->ch[rel] = ch[rel ^ 1]; if (ch[rel ^ 1]) ch[rel ^ 1]->fa = t; ch[rel ^ 1] = t; t->fa = this; t->Pull(); Pull(); } void Splay() { while (fa) { if (!fa->fa) { Rotate(); continue; } fa->fa->Push(); fa->Push(); if (Relation() == fa->Relation()) fa->Rotate(); else Rotate(); Rotate(); } } void Evert() { Access(); Splay(); rev ^= true; } void Expose() { Splay(); Push(); if (ch[1]) { ch[1]->fa = nullptr; ch[1]->pfa = this; ch[1] = nullptr; Pull(); } } bool Splice() { Splay(); if (!pfa) return false; pfa->Expose(); pfa->ch[1] = this; fa = pfa; pfa = nullptr; fa->Pull(); return true; } void Access() { Expose(); while (Splice()); } }; vector<Node *> node; size_t num_node; LinkCutTree() = default; template <class U> LinkCutTree(const vector<U> &info) : num_node(info.size()) { node.assign(num_node, nullptr); for (size_t i = 0; i < num_node; ++i) node[i] = new Node(info[i]); } void Link(size_t u, size_t v) const { node[v]->Evert(); node[v]->pfa = node[u]; } void Cut(size_t u, size_t v) const { node[u]->Evert(); node[v]->Access(); node[v]->Splay(); node[v]->Push(); node[v]->ch[0]->fa = nullptr; node[v]->ch[0] = nullptr; node[v]->Pull(); } void Modify(size_t u, const InfoType &v) const { node[u]->Splay(); node[u]->info += v; node[u]->Pull(); } template <class ...Args> void Update(size_t u, Args&& ...args) const { node[u]->Splay(); node[u]->info = InfoType(forward<Args>(args)...); node[u]->Pull(); } SumType Query(size_t u, size_t v) const { node[u]->Evert(); node[v]->Access(); node[v]->Splay(); return node[v]->sum; } }; int main() { int n, q; scanf("%d%d", &n, &q); vector<int> a(n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); LinkCutTree<int64_t, int64_t> lct(a); for (int i = 0; i < n - 1; ++i) { int u, v; scanf("%d%d", &u, &v); lct.Link(u, v); } while (q--) { int t; scanf("%d", &t); if (t == 0) { int u, v, w, x; scanf("%d%d%d%d", &u, &v, &w, &x); lct.Cut(u, v); lct.Link(w, x); } if (t == 1) { int p, x; scanf("%d%d", &p, &x); lct.Modify(p, x); } if (t == 2) { int u, v; scanf("%d%d", &u, &v); printf("%lld\n", lct.Query(u, v)); } } }