Submit Info #12575

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp14 Tweetuzki AC 272 ms 11.42 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 267 ms 11.42 MiB
max_random_01 AC 263 ms 11.37 MiB
max_random_02 AC 272 ms 11.42 MiB
random_00 AC 174 ms 7.61 MiB
random_01 AC 193 ms 8.80 MiB
random_02 AC 119 ms 3.75 MiB
random_03 AC 83 ms 9.06 MiB
random_04 AC 80 ms 1.67 MiB
small_00 AC 3 ms 0.67 MiB
small_01 AC 0 ms 0.67 MiB
small_02 AC 1 ms 0.68 MiB

#include <algorithm> #include <cstdio> #include <cstring> const int MaxN = 200000; struct graph_t { int cnte; int head[MaxN + 5], to[MaxN * 2 + 5], next[MaxN * 2 + 5]; inline void addEdge(int u, int v) { cnte++; to[cnte] = v; next[cnte] = head[u]; head[u] = cnte; } }; int N, Q; int A[MaxN + 5]; graph_t Gr; namespace lct { #define lson ch[0] #define rson ch[1] int fa[MaxN + 5], ch[2][MaxN + 5]; long long val[MaxN + 5], sum[MaxN + 5]; bool rev[MaxN + 5]; inline int getson(int x, int f) { return rson[f] == x; } inline bool isroot(int x) { return lson[fa[x]] != x && rson[fa[x]] != x; } inline void reverse(int x) { std::swap(lson[x], rson[x]); rev[x] ^= 1; } inline void update(int x) { sum[x] = sum[lson[x]] + sum[rson[x]] + val[x]; } inline void pushdown(int x) { if (rev[x] == true) { if (lson[x] != 0) reverse(lson[x]); if (rson[x] != 0) reverse(rson[x]); rev[x] = false; } } inline void rotate(int x) { int f = fa[x], g = fa[f]; int l = getson(x, f); if (ch[l ^ 1][x] != 0) fa[ch[l ^ 1][x]] = f; if (isroot(f) == false) ch[getson(f, g)][g] = x; ch[l][f] = ch[l ^ 1][x], ch[l ^ 1][x] = f; fa[x] = g, fa[f] = x; update(f); } inline void erasetag(int x) { if (isroot(x) == false) erasetag(fa[x]); pushdown(x); } inline void splay(int x) { erasetag(x); while (isroot(x) == false) { int f = fa[x], g = fa[f]; if (isroot(f) == false) { if (getson(x, f) == getson(f, g)) rotate(f); else rotate(x); } rotate(x); } update(x); } inline void access(int f) { int x = 0; while (f != 0) { splay(f); rson[f] = x; update(f); x = f, f = fa[f]; } } inline void makeroot(int x) { access(x); splay(x); reverse(x); } inline void link(int x, int y) { makeroot(y); fa[y] = x; } inline void split(int x, int y) { makeroot(x); access(y); splay(y); } inline void cut(int x, int y) { split(x, y); lson[y] = 0; fa[x] = 0; update(y); } #undef lson #undef rson } void init() { scanf("%d %d", &N, &Q); for (int i = 1; i <= N; ++i) scanf("%d", &A[i]); for (int i = 1; i < N; ++i) { int u, v; scanf("%d %d", &u, &v); u++, v++; Gr.addEdge(u, v); Gr.addEdge(v, u); } } void dfs(int u) { for (int i = Gr.head[u]; i; i = Gr.next[i]) { int v = Gr.to[i]; if (v == lct::fa[u]) continue; lct::fa[v] = u; dfs(v); } } void solve() { for (int i = 1; i <= N; ++i) lct::val[i] = A[i]; dfs(1); for (int q = 1; q <= Q; ++q) { int opt; scanf("%d", &opt); if (opt == 0) { int u, v, w, x; scanf("%d %d %d %d", &u, &v, &w, &x); u++, v++, w++, x++; lct::cut(u, v); lct::link(w, x); } else if (opt == 1) { int p, x; scanf("%d %d", &p, &x); p++; lct::splay(p); lct::val[p] += x; lct::update(p); } else { int u, v; scanf("%d %d", &u, &v); u++, v++; lct::split(u, v); printf("%lld\n", lct::sum[v]); } } } int main() { init(); solve(); return 0; }