本文共 3108 字，大约阅读时间需要 10 分钟。
题目大意：
#include #include //#include #include #include #include #include #include #include #include //#include #define lson (o<<1)#define rson ((o<<1)|1)#define CLR(a,b) memset(a,b,sizeof(a))#define mkp(a,b) make_pair(a,b)typedef long long ll;using namespace std;const int maxn=100010;vector edge[maxn];int n,m,op,x,tot,val[maxn],l[maxn],r[maxn],deep[maxn],son[maxn],fa[maxn],top[maxn],fin[maxn];ll sum[maxn<<3],lazy[maxn<<3],size[maxn<<3];inline void dfs_1(int x,int pre){ fa[x] = pre; son[x] = -1; size[x] = 1; deep[x] = deep[pre]+1; for(int i = 0; i < edge[x].size(); i++) if(edge[x][i] != pre) { dfs_1(edge[x][i],x); size[x] += size[edge[x][i]]; if(son[x]==-1 || size[edge[x][i]]>size[son[x]]) son[x] = edge[x][i]; }}inline void dfs_2(int x,int root){ top[x] = root; l[x] = ++tot; fin[l[x]] = x; if(son[x] != -1) dfs_2(son[x],root); for(int i = 0; i < edge[x].size(); i++) if(edge[x][i] != fa[x] && edge[x][i] != son[x]) dfs_2(edge[x][i],edge[x][i]); r[x]=tot;}inline void maintain(int o,int l,int r){ if(l!=r)sum[o]=sum[lson]+sum[rson];}inline void pushdown(int o,int l,int r){ if(lazy[o]) { sum[lson]+=size[lson]*lazy[o]; sum[rson]+=size[rson]*lazy[o]; lazy[lson]+=lazy[o]; lazy[rson]+=lazy[o]; } lazy[o]=0;}inline void build(int o,int l,int r){ if(l==r) { sum[o]=(ll)val[fin[l]]; size[o]=1; return; } int mid = (l+r)/2; build(lson,l,mid); build(rson,mid+1,r); maintain(o,l,r); size[o]=size[lson]+size[rson];}inline void update(int o,int l,int r,int L,int R,int v){ pushdown(o,l,r); if(R r)return; if(l>=L && r<=R) { lazy[o]+=(ll)v; sum[o]+=((ll)size[o])*((ll)v); return; } int mid=(l+r)>>1; update(lson,l,mid,L,R,v); update(rson,mid+1,r,L,R,v); maintain(o,l,r);}inline ll query(int o,int l,int r,int L,int R){ pushdown(o,l,r); if(R r)return 0; if(l>=L && r<=R)return sum[o]; int mid=(l+r)>>1; return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);}inline ll get(int x){ ll ret = 0; while(top[x]!=1) { ret+=query(1,1,n,l[top[x]],l[x]); x=fa[top[x]]; } ret+=query(1,1,n,1,l[x]); return ret;}int main(){ scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&val[i]),sum[i]=i; int u,v; for(int i = 1; i < n; i++) { scanf("%d%d",&u,&v); edge[u].push_back(v); edge[v].push_back(u); } dfs_1(1,0); dfs_2(1,1); build(1,1,n); for(int i = 0; i < m; i++) { scanf("%d%d",&op,&x); if(op==1) { scanf("%d",&v); update(1,1,n,l[x],l[x],v); } if(op==2) { scanf("%d",&v); update(1,1,n,l[x],r[x],v); } if(op==3)printf("%lld\n",get(x)); } return 0;}
转载于:https://www.cnblogs.com/mountaink/p/9886628.html