Submit Info #7134

Problem Lang User Status Time Memory
Dynamic Tree Vertex Add Path Sum cpp KaedeTakagaki AC 549 ms 13.66 MiB

ケース詳細
Name Status Time Memory
example_00 AC 3 ms 0.68 MiB
max_random_00 AC 549 ms 13.66 MiB
max_random_01 AC 540 ms 13.65 MiB
max_random_02 AC 544 ms 13.61 MiB
random_00 AC 331 ms 9.05 MiB
random_01 AC 389 ms 10.40 MiB
random_02 AC 181 ms 4.42 MiB
random_03 AC 214 ms 10.93 MiB
random_04 AC 112 ms 1.92 MiB
small_00 AC 6 ms 0.71 MiB
small_01 AC 4 ms 0.67 MiB
small_02 AC 2 ms 0.68 MiB

//Let's join Kaede Takagaki Fan Club !! #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define all(x) x.begin(),x.end() template<class T> void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template<class T> bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template<class T> bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template<class T> void g(T &a){ cin >> a; } template<class T> void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; template<class T> void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } ll a[200005]; struct dat { ll sum; //reverseする void rv(){ //lol } }; //自作コンストラクタ dat dt(ll a){ dat ret; ret.sum = a; return ret; } //a, b をこの順にマージする dat mrg(dat a, dat b){ dat ret; ret.sum = a.sum + b.sum; return ret; } struct node{ node *l, *r, *p; int id, rev; dat D; node(int i) : l(0), r(0), p(0), id(i), rev(0){ //Dに実データを持つ D = dt(a[i]); } }; inline bool is_root(node *n){ return n -> p == NULL || n -> p -> l != n && n -> p -> r != n; } inline bool left(node *n){ return n == n -> p -> l; } //遅延評価 //push(n)を走らせた後にはn->l と n->r の値は正しく計算されている必要あり inline void push(node *n){ if(n->rev){ swap(n->l, n->r); if(n->l){ n->l->rev ^= 1; n->l->D.rv(); } if(n->r){ n->r->rev ^= 1; n->r->D.rv(); } n->rev = 0; } } //値の再計算 inline void update(node *n){ //最初に遅延評価 push(n); dat slf = dt(a[n->id]); if(n->l) slf = mrg(n->l->D, slf); if(n->r) slf = mrg(slf, n->r->D); n->D = slf; } inline void connect(node *n, node *p, bool l){ (l ? p -> l : p -> r) = n; if(n) n -> p = p; } //rotateが呼ばれる前には関与しているノードの遅延評価をする必要がある inline void rotate(node *n){ node *p = n -> p, *g = p -> p; bool l = left(n); connect(l ? n -> r : n -> l, p, l); if(!is_root(p)) connect(n, g, left(p)); else n -> p = g; connect(p, n, !l); update(p), update(n); } inline void splay(node *n){ while(!is_root(n)){ node *p = n -> p, *g = p -> p; //関与する頂点群の遅延評価をする if(!is_root(p)) push(g); push(p), push(n); if(!is_root(p)) rotate(left(n) ^ left(p) ? n : p); rotate(n); } //最後に遅延評価 update(n); //push(n); } //返り値はnじゃないよ inline node* expose(node *n){ node *last = NULL; for(node *m = n; m; m = m -> p){ splay(m); m -> r = last; last = m; //if(!m->p){ // update(m); // break; //} } splay(n); return last; } inline void link(node *m, node *n){ expose(m), expose(n); m -> p = n; } inline void cut(node *n){ expose(n); n -> l -> p = NULL; n -> l = NULL; update(n); } //nを根に持っていく //updateは必要ない inline void evert(node *n){ expose(n); n->rev ^= 1; n->D.rv(); } const int MAXN = 200005; node *V[MAXN]; int n,q; int main(){ scanf("%d%d",&n,&q); rep(i,n){ scanf("%lld",&a[i]); V[i] = new node(i); } rep(i,n-1){ int u, v; scanf("%d %d",&u, &v); evert(V[u]); link(V[u], V[v]); } rep(i,q){ int ty; scanf("%d",&ty); if(ty == 0){ int u, v, w, x; scanf("%d%d%d%d",&u,&v,&w,&x); evert(V[u]); cut(V[v]); evert(V[w]); link(V[w], V[x]); } else if(ty == 1){ int p,x; scanf("%d%d",&p,&x); a[p] += x; evert(V[p]); update(V[p]); } else{ int u, v; scanf("%d%d",&u,&v); evert(V[u]); expose(V[v]); printf("%lld\n",V[v]->D.sum); } } }