1 条题解
-
0

#include <bits/stdc++.h> #define pa p[nd] #define root nd[0].c[0] #define maxV 256101 using namespace std; typedef long long ll; struct node{ ll v, s, st, sa, as, m; int tag_add, tag_adj; int sz, rev, c[2], p; }nd[maxV]; int n, q, i; int x, y; ll z; inline int dir(int x){return !x[nd].p ? -1 : x == x[nd].pa.c[0] ? 0 : x == x[nd].pa.c[1] ? 1 : -1;} void reverse(int x){swap(x[nd].c[0], x[nd].c[1]); x[nd].rev ^= 1;} void adj(int x, ll y){ if(!x) return; x[nd].v = x[nd].m = y; x[nd].s = y * x[nd].sz; x[nd].tag_adj = y; x[nd].tag_add = 0; x[nd].sa = x[nd].s + x[nd].st; } void add(int x, ll y){ if(!x) return; x[nd].v += y; x[nd].s += y * x[nd].sz; x[nd].m += y; x[nd].tag_adj ? x[nd].tag_adj += y : x[nd].tag_add += y; x[nd].sa = x[nd].s + x[nd].st; } void push_down(int x){ if(x[nd].rev){ reverse(x[nd].c[0]); reverse(x[nd].c[1]); x[nd].rev = 0; } if(x[nd].tag_adj){ adj(x[nd].c[0], x[nd].tag_adj); adj(x[nd].c[1], x[nd].tag_adj); x[nd].tag_adj = 0; } if(x[nd].tag_add){ add(x[nd].c[0], x[nd].tag_add); add(x[nd].c[1], x[nd].tag_add); x[nd].tag_add = 0; } } void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);} inline void up(ll &x, const ll y){x < y ? x = y : 0;} void update(int x){ x[nd].s = x[nd].m = x[nd].v; x[nd].st = x[nd].as; x[nd].sz = 1; int lc = x[nd].c[0], rc = x[nd].c[1]; if(lc){ x[nd].sz += lc[nd].sz; x[nd].s += lc[nd].s; up(x[nd].m, lc[nd].m); x[nd].st += lc[nd].st; } if(rc){ x[nd].sz += rc[nd].sz; x[nd].s += rc[nd].s; up(x[nd].m, rc[nd].m); x[nd].st += rc[nd].st; } x[nd].sa = x[nd].s + x[nd].st; } void rotate(int x){ int y = x[nd].p, d = !dir(x); nd[y[nd].c[!d] = x[nd].c[d]].p = y; x[nd].p = y[nd].p; if(~dir(y)) y[nd].pa.c[dir(y)] = x; nd[x[nd].c[d] = y].p = x; update(y); update(x); } void splay(int x){for(pull_down(x); ~dir(x); rotate(x)) if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);} void access(int x){ for(int y = 0; x; y = x, x = x[nd].p){ splay(x); if(x[nd].c[1]) x[nd].as += x[nd].c[1][nd].sa; if(x[nd].c[1] = y) x[nd].as -= y[nd].sa; update(x); } } void make_root(int x){access(x); splay(x); reverse(x);} int find_root(int x){access(x); splay(x); for(; x[nd].c[0]; x = x[nd].c[0]); return x;} void link(int x, int y){ make_root(x); make_root(y); x[nd].p = y; y[nd].as += x[nd].sa; access(x); } void split(int x, int y){make_root(x); access(y); splay(y);} void cut(int x, int y){split(x, y); x[nd].p = y[nd].c[0] = 0; update(y);} int main(){ scanf("%d", &n); for(i = 1; i <= n; i++){ scanf("%lld", &z); nd[i].v = nd[i].s = nd[i].m = nd[i].sa = z; nd[i].sz = 1; } for(i = 2; i <= n; i++){ scanf("%d", &x); link(x, i); } for(scanf("%d", &q); q; --q) switch(scanf("%d%d%d", &i, &x, &y), i){ case 1:{ scanf("%lld", &z); split(x, y); add(y, z); break; } case 2:{ scanf("%lld", &z); split(x, y); adj(y, z); break; } case 3:{ split(x, y); printf("%lld\n", nd[y].as + nd[y].v); break; } case 4:{ split(x, y); printf("%lld\n", nd[y].m); break; } case 5:{ split(x, y); printf("%lld\n", nd[y].s); break; } case 6: link(x, y); break; case 7: cut(x, y); break; } return 0; }
- 1
信息
- ID
- 6054
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者