没什么好说的啊 练基本功啊
时间戳+线段树成段更新+单点查询
用dfs时间戳找出每个人管的属下 low high
每次成段更新 唉
#include#include #include using namespace std; const int MAX = 500010; int b[MAX]; int c[MAX]; int low[MAX]; int high[MAX]; vector e[MAX]; int cnt = 0; struct node { __int64 sum; __int64 add; }a[MAX*4]; void build(int l, int r, int rt) { a[rt].add = 0; if(l == r) { a[rt].sum = b[c[l]]; return; } int m = (l + r) >> 1; build(l, m, rt<<1); build(m+1, r, rt<<1|1); a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum; } void update(int x, int y, int l, int r, int rt, int add) { if(x == l && y == r) { a[rt].add += (__int64)add; a[rt].sum += (__int64)(r - l + 1) * add; return; } if(a[rt].add) { int k = (r - l + 1); a[rt<<1].add += a[rt].add ; a[rt<<1|1].add += a[rt].add; a[rt<<1].sum += (k - (k >> 1)) * a[rt].add; a[rt<<1|1].sum += (k >> 1) * a[rt].add; a[rt].add = 0; } int m = (l + r) >> 1; if(y <= m) update(x, y, l, m, rt<<1, add); else if(x > m) update(x, y, m+1, r, rt<<1|1, add); else { update(x, m, l, m, rt<<1, add); update(m+1, y, m+1, r, rt<<1|1, add); } a[rt].sum = a[rt<<1].sum + a[rt<<1|1].sum; } __int64 query(int l, int r, int x, int rt) { if(l == x && r == x) return a[rt].sum; if(a[rt].add) { int k = (r - l + 1); a[rt<<1].add += a[rt].add ; a[rt<<1|1].add += a[rt].add; a[rt<<1].sum += (k - (k >> 1)) * a[rt].add; a[rt<<1|1].sum += (k >> 1) * a[rt].add; a[rt].add = 0; } int m = (l + r) >> 1; if(x <= m) return query(l, m, x, rt<<1); else return query(m+1, r, x, rt<<1|1); } void dfs(int u) { low[u] = ++cnt; c[cnt] = u; for(int i = 0;i < e[u].size(); i++) { int v = e[u][i]; //c[cnt] += b[v]; dfs(v); } high[u] = cnt; } int main() { int n, m; char str[10]; scanf("%d %d",&n, &m); for(int i = 1; i <= n; i++) { if(i == 1) scanf("%d", &b[i]); else { int x; scanf("%d %d", &b[i], &x); e[x].push_back(i); } } dfs(1); //printf("%d\n", cnt); build(1, n, 1); while(m--) { scanf("%s", str); if(str[0] == 'p') { int x, y; scanf("%d %d", &x, &y); if(low[x] == high[x]) continue; update(low[x]+1, high[x], 1, n, 1, y); } else { int x; scanf("%d", &x); printf("%I64d\n", query(1, n, low[x], 1)); } } return 0; }