BZOJ-4034: [HAOI2015]樹上操作 (線段樹+DFS序)

4034: [HAOI2015]樹上操作

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 5879  Solved: 1897

[​​Submit​​​][​​Status​​​][​​Discuss​​]

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

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<n;i++){
70         u=read(),v=read();
71         addedge(u,v),addedge(v,u);
72     }
73     fa[1]=0,dfs(1);
74     for (i=1;i<=n;i++) update(1,1,n,cc[i],cc[i],a[i]);
75     for (i=1;i<=m;i++){
76         z=read();
77         if (z==1) x=read(),y=read(),update(1,1,n,cc[x],cc[x],y);
78         if (z==2) x=read(),y=read(),update(1,1,n,cc[x],vv[x],y);
79         if (z==3) x=read(),printf("%lld\n",calc(x));
80     }
81     return 0;
82