|
题目描述 Description
|
|
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
|
|
输入描述 Input Description
|
|
第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1
行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中
第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
|
|
输出描述 Output Description
|
|
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
|
|
样例输入 Sample Input
|
|
5 5
1 2 3 4 5 1 2 1 4 2 3 2 5 3 3 1 2 1 3 5 2 1 2 3 3 |
|
样例输出 Sample Output
|
|
6
9 13 |
|
数据范围及提示 Data Size & Hint
|
|
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
|
本题和树链剖分裸题唯一的区别就是本题有修改子树这种操作。不过我们不要慌，再仔细想一想树链剖分能支持做的事情：对一段区间进行修改。很巧的是子树由于DFS的原因就是在一个连续的区间里，于是我们用两个数组l,r表示当前节点对应子树的区间，在divide的时候记录一下即可。
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; #define mem(a,b) memset(a,b,sizeof(a)) typedef pair<int,int> PII; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();} return x*f; } const int maxn=100010; int n,q,cost[maxn],w[maxn],first[maxn],fa[maxn],id[maxn],bl[maxn],size[maxn],a,b,tp,ce=-1,es,l[maxn],r[maxn],maxs[maxn]; LL tag[maxn<<2],sum[maxn<<2]; struct Edge { int u,v,next; Edge() {} Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {} }e[maxn<<1]; void addEdge(int a,int b) { e[++ce]=Edge(a,b,first[a]);first[a]=ce; e[++ce]=Edge(b,a,first[b]);first[b]=ce; } void dfs(int now,int pa) { size[now]=1; for(int i=first[now];i!=-1;i=e[i].next) if(e[i].v!=pa) { fa[e[i].v]=now; dfs(e[i].v,now); size[now]+=size[e[i].v]; if(size[e[i].v]>size[maxs[now]])maxs[now]=e[i].v; } return; } void divide(int now,int chain) { bl[now]=chain;id[now]=++es;l[now]=es; if(maxs[now])divide(maxs[now],chain); for(int i=first[now];i!=-1;i=e[i].next)if(e[i].v!=fa[now] && e[i].v!=maxs[now])divide(e[i].v,e[i].v); r[now]=es; return; } void pushdown(int l,int r,int o) { int mid=(l+r)>>1,lo=o<<1,ro=lo|1; if(l==r){tag[o]=0;return;} tag[lo]+=tag[o];tag[ro]+=tag[o]; sum[lo]+=(LL)(mid-l+1)*tag[o]; sum[ro]+=(LL)(r-mid)*tag[o]; tag[o]=0; } void build(int l,int r,int o) { if(l==r) { sum[o]=w[l]; return; } int mid=(l+r)>>1,lo=o<<1,ro=lo|1; build(l,mid,lo);build(mid+1,r,ro); sum[o]=sum[lo]+sum[ro]; return; } void update(int l,int r,int o,int a,int b,int c) { if(l==a && r==b) { tag[o]+=c; sum[o]+=(LL)(r-l+1)*c; return; } pushdown(l,r,o); int mid=(l+r)>>1,lo=o<<1,ro=lo|1; if(b<=mid)update(l,mid,lo,a,b,c); else if(a>mid)update(mid+1,r,ro,a,b,c); else update(l,mid,lo,a,mid,c),update(mid+1,r,ro,mid+1,b,c); sum[o]=sum[lo]+sum[ro]+tag[o]*(r-l+1); return; } LL sectionsum(int l,int r,int o,int a,int b) { if(l==a && r==b)return sum[o]; int mid=(l+r)>>1,lo=o<<1,ro=lo|1; pushdown(l,r,o); if(b<=mid)return sectionsum(l,mid,lo,a,b); else if(a>mid)return sectionsum(mid+1,r,ro,a,b); else return sectionsum(l,mid,lo,a,mid)+sectionsum(mid+1,r,ro,mid+1,b); } LL query(int a) { LL ans=0; while(bl[a]!=1) { ans+=sectionsum(1,n,1,id[bl[a]],id[a]); a=fa[bl[a]]; } ans+=sectionsum(1,n,1,1,id[a]); return ans; } int main() { mem(first,-1); n=read();q=read(); for(int i=1;i<=n;i++)cost[i]=read(); for(int i=1;i<n;i++)a=read(),b=read(),addEdge(a,b); dfs(1,-1);divide(1,1); for(int i=1;i<=n;i++)w[id[i]]=cost[i]; build(1,n,1); while(q--) { tp=read();a=read(); if(tp==3)printf("%lld ",query(a)); else { b=read(); if(tp==1)update(1,n,1,l[a],l[a],b); else update(1,n,1,l[a],r[a],b); } } return 0; }