题目链接

bzoj4034: [HAOI2015]树上操作

题解

树剖线段树

代码

#include<bits/stdc++.h> using namespace std; inline int read() { int x = 0,f = 1; char c = getchar(); while(c < '0' ||c > '9'){if(c == '-')f= -1; c = getchar();} while(c <= '9' &&c >= '0')x = x * 10 + c- '0',c = getchar(); return x * f; } #define int long long const int maxn = 200007; int n,m,val[maxn]; struct node { int u,v,next; } edge[maxn << 1]; int head[maxn],num; inline void add_edge(int u,int v) { edge[++ num].v = v; edge[num].next = head[u];head[u] = num ; } int fa[maxn],deep[maxn],siz[maxn],son[maxn]; void dfs1(int x) { deep[x] = deep[fa[x]] + 1;siz[x] = 1; for(int i = head[x];i ;i = edge[i].next) { int v = edge[i].v; if(deep[v]) continue; fa[v] = x; dfs1(v); siz[x] += siz[v]; if(siz[v] > siz[son[x]] || !son[x]) son[x] = v; } } int pos[maxn],_pos,sop[maxn],top[maxn]; void dfs2(int x,int topfa) { top[x] = topfa;pos[x] = ++_pos;sop[_pos] = x; if(!son[x]) return ; dfs2(son[x],topfa); for(int i = head[x];i;i = edge[i].next) { int v = edge[i].v; if(v == son[x] || v == fa[x]) continue; dfs2(v,v); } } #define lc rt << 1 #define rc rt << 1 | 1 int sum[maxn << 2],tag[maxn << 2]; inline void update(int rt) {sum[rt] = sum[lc] + sum[rc]; } void build(int rt,int l,int r) { if(l == r) { sum[rt] = val[sop[l]];return ; } int mid = l + r >> 1; build(lc,l,mid); build(rc,mid + 1,r); return update(rt); } inline void pushdown(int rt,int l,int r) { int mid = l + r >> 1; tag[lc] += tag[rt];tag[rc] += tag[rt]; sum[lc] += (mid - l + 1) * tag[rt]; sum[rc] += (r - mid) * tag[rt]; tag[rt] = 0; } int T_query(int rt,int l,int r,int tl,int tr ){ if(l >= tl && r <= tr) return sum[rt]; if(tag[rt] != 0) pushdown(rt,l,r); int mid = l + r >> 1,Ret = 0 ; if(tl <= mid) Ret += T_query(lc,l,mid,tl,tr); if(tr > mid) Ret += T_query(rc,mid + 1,r,tl,tr); return Ret; } void T_modify(int rt,int l,int r,int tl,int tr,int a) { if(l >= tl && r <= tr) { sum[rt] += (r - l + 1) * a; tag[rt] += a; return ; } if(tag[rt] != 0)pushdown(rt,l,r); int mid = l + r >> 1; if(tl <= mid) T_modify(lc,l,mid,tl,tr,a); if(tr > mid) T_modify(rc,mid + 1,r,tl,tr,a); update(rt); } int Q(int x) { int ret = 0 ; for(;top[x] != 1;x = fa[top[x]]) ret += T_query(1,1,n,pos[top[x]],pos[x]); ret += T_query(1,1,n,pos[top[x]],pos[x]); return ret; } void M1(int x,int a) { T_modify(1,1,n,pos[x],pos[x],a); } void M2(int x,int a) { T_modify(1,1,n,pos[x],pos[x] + siz[x] - 1,a); } main() { n = read(),m = read(); for(int i = 1;i <= n;++ i) val[i] = read(); for(int u,v,i = 1;i < n;++ i) { u = read(); v = read(); add_edge(u,v); add_edge(v,u); } dfs1(1); dfs2(1,1); build(1,1,n); for(int type,x,a;m --;) { type = read(); if(type == 1) { x = read(); a = read(); M1(x,a); } else if(type == 2) { x = read(); a = read(); M2(x,a); } else { x = read(); printf("%lld\n",Q(x)) ; } } return 0; }

转载于:https://www.cnblogs.com/sssy/p/9282061.html