Submit Info #33659

Problem Lang User Status Time Memory
Dynamic Tree Subtree Add Subtree Sum cpp Binario AC 1648 ms 101.05 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.62 MiB
max_random_00 AC 1580 ms 101.05 MiB
max_random_01 AC 1648 ms 101.05 MiB
max_random_02 AC 1647 ms 100.98 MiB
max_random_03 AC 1612 ms 100.98 MiB
max_random_04 AC 1522 ms 100.99 MiB
random_00 AC 989 ms 68.06 MiB
random_01 AC 1056 ms 75.96 MiB
random_02 AC 564 ms 37.92 MiB
random_03 AC 459 ms 62.17 MiB
random_04 AC 371 ms 21.43 MiB
small_00 AC 3 ms 0.92 MiB
small_01 AC 3 ms 0.79 MiB
small_02 AC 2 ms 0.77 MiB
small_03 AC 3 ms 0.80 MiB
small_04 AC 5 ms 0.92 MiB

/** * Euler Tour Tree - SubTree Add, SubTreeSum * * Complexity: * - Time: O(lg n) amortized per operation * - Space: O(n) * * https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum * */ #include <bits/stdc++.h> using namespace std; #define FOR(i, b) for(int i = 0; i < (b); i++) #define endl '\n' using vi = vector<int>; using ll = long long; using ii = pair<int, int>; template <class U> struct EulerTree{ struct Node{ U val, dp, lazy; int sz, szR, prior; // szR = real size, excluding the edges Node *l = NULL, *r = NULL, *p = NULL; bool vtx; // is vertex Node (U val, bool vtx = true): val(val), dp(val), lazy(0), sz(1), szR(vtx), prior(rand()), vtx(vtx){} }; using Treap = Node*; vector<Treap> T; vector<map<int, pair<Treap, Treap>>> edges; EulerTree(int n) : T(n), edges(n){} int szR(Treap t){ return t ? t->szR : 0; } int sz (Treap t) { return t ? t->sz : 0; } void add(Treap t, U val){ if(t){ t->lazy += val; t->dp += t->szR * val; } } void pull(Treap t){ t->dp = t->val + (t->l ? t->l->dp : 0) + (t->r ? t->r->dp : 0); } void push(Treap t){ U& lazy = t->lazy; if(t && lazy){ add(t->l, lazy); add(t->r, lazy); if(t->vtx) t->val += lazy; lazy = 0; } } void update (Treap t) { if (t){ pull(t); t->sz = 1 + sz(t->l) + sz(t->r); t->szR = t->vtx + szR(t->l) + szR(t->r); t->p = NULL; if(t->l) t->l->p = t; if(t->r) t->r->p = t; } } void merge (Treap & t, Treap l, Treap r) { push(l); push(r); if (!l || !r) t = l ? l : r; else if (l->prior > r->prior) merge (l->r, l->r, r), t = l; else merge (r->l, l, r->l), t = r; update (t); } void split (Treap t, Treap & l, Treap & r, int key, int add = 0) { push(t); if (!t) return void( l = r = NULL ); int cur_key = add + sz(t->l); //implicit key if (key <= cur_key) split (t->l, l, t->l, key, add), r = t; else split (t->r, t->r, r, key, add + 1 + sz(t->l)), l = t; update(t); } pair<Treap, int> getPos(Treap t){ int pos = sz(t->l); while(t->p){ bool isRight = t->p->r == t; t = t->p; if(isRight) pos += 1 + sz(t->l); } return {t, pos}; } Treap makeRoot(int v){ Treap t; auto pr = getPos(T[v]); split(pr.first, pr.first, t, pr.second); merge(t, t, pr.first); return t; } void Set(int v, U val){ T[v] = new Node(val); } void AddTree(int v, U val){ add(getPos(T[v]).first, val); } U Sum(int v){ return getPos(T[v]).first->dp; } void Link(int v, int u){ if(v > u) swap(v, u); Treap tv = makeRoot(v); Treap tu = makeRoot(u); Treap e1 = new Node(0, false); Treap e2 = new Node(0, false); edges[v][u] = {e1, e2}; merge(tv, tv, e1); merge(tv, tv, tu); merge(tv, tv, e2); } void Cut(int v, int u){ if(v > u) swap(v, u); assert(edges[v].count(u)); auto edge = edges[v][u]; edges[v].erase(u); auto prv = getPos(edge.first); auto pru = getPos(edge.second); Treap t = prv.first, after, tmp; int pos1 = prv.second; int pos2 = pru.second; if(pos1 > pos2) swap(pos1, pos2); split(t, t, after, pos2 + 1); split(t, t, tmp, pos2); split(t, t, tmp, pos1 + 1); split(t, t, tmp, pos1); merge(t, t, after); } }; int main(){ cin.tie(0)->sync_with_stdio(0); int n, q, u, v, val, tp, w, x, p; cin >> n >> q; EulerTree<long long> ETT(n); FOR(i, n){ cin >> val; ETT.Set(i, val); } FOR(i, n - 1){ cin >> u >> v; ETT.Link(u, v); } FOR(i, q){ cin >> tp; switch (tp) { case 0: cin >> u >> v >> w >> x; ETT.Cut(u, v); ETT.Link(w, x); break; case 1: cin >> v >> p >> val; ETT.Cut(v, p); ETT.AddTree(v, val); ETT.Link(v, p); break; case 2: cin >> v >> p; ETT.Cut(v, p); cout << ETT.Sum(v) << endl; ETT.Link(v, p); } } }