4034: [HAOI2015]树上操作

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 5879  Solved: 1897

[][][]

Description

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。

操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

Input

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 

行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中

第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

 

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

 

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

HINT

 

 对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。

 

Source

假装我过了←_← 辣鸡TLE

1 #include "bits/stdc++.h" 2 #define lson rt<<1,l,m 3 #define rson rt<<1|1,m+1,r 4 using namespace std; 5 typedef long long LL; 6 const int MAX=1e5+5; 7 LL n,m,a[MAX]; 8 LL tot,head[MAX],adj[MAX],next[MAX]; 9 LL tx,cc[MAX],vv[MAX],fa[MAX];10 LL c[MAX<<2],la[MAX<<2];11 bool vis[MAX];12 inline LL read(){13     LL an=0,x=1;char c=getchar();14     while (c<'0' || c>'9') {
    if (c=='-') x=-1;c=getchar();}15     while (c>='0' && c<='9') {an=an*10+c-'0';c=getchar();}16     return an*x;17 }18 void addedge(int u,int v){tot++; adj[tot]=v; next[tot]=head[u]; head[u]=tot;}19 void PushUp(int rt){20     c[rt]=c[rt<<1]+c[rt<<1|1];21 }22 void PushDown(int rt,int l,int r){23     int m=(l+r)>>1;24     if (la[rt]){25         la[rt<<1]+=la[rt],la[rt<<1|1]+=la[rt];26         c[rt<<1]+=la[rt]*(m-l+1);27         c[rt<<1|1]+=la[rt]*(r-m);28         la[rt]=0;29     }30 }31 void update(int rt,int l,int r,int x,int y,LL z){32     if (x<=l && r<=y){33         la[rt]+=z; c[rt]+=(r-l+1)*z;34         return;35     }36     int m=(l+r)>>1;37     PushDown(rt,l,r);38     if (x<=m) update(lson,x,y,z);39     if (y>m) update(rson,x,y,z);40     PushUp(rt);41 }42 LL query(int rt,int l,int r,LL x){43     if (l==r && l==x)44         return c[rt];45     int m=(l+r)>>1;LL cnt=0;46     PushDown(rt,l,r);47     if (x<=m) cnt+=query(lson,x);48     else cnt+=query(rson,x);49     return cnt;50 }51 void dfs(int x){52     cc[x]=++tx;vis[x]=true;53     int i,j;54     for (i=head[x];i;i=next[i])55         if (!vis[adj[i]])56             fa[adj[i]]=x,dfs(adj[i]);57     vv[x]=tx;58 }59 LL calc(int x){60     if (x==1) return query(1,1,n,cc[x]);61     return query(1,1,n,cc[x])+calc(fa[x]);62 }63 int main(){64     freopen ("tree.in","r",stdin);65     freopen ("tree.out","w",stdout);66     int i,j,x,y,z,u,v;67     n=read(),m=read();68     for (i=1;i<=n;i++) a[i]=read();69     for (i=1;i