4034. [HAOI2015]树上操作【树链剖分】

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 。

一道裸的树剖却因为建树时候的sb错误搞了半天
不想说什么（不过这个题好像会炸int）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #define LL long long
  5 #define MAXN (100000+50)
  6 using namespace std;
  7 LL Tree[MAXN];
  8 LL T_num[MAXN];
  9 LL Depth[MAXN];
 10 LL Father[MAXN];
 11 LL Sum[MAXN];
 12 LL Son[MAXN];
 13 LL Top[MAXN];
 14 LL a[MAXN];
 15 LL n,m,u,v,sum;
 16 LL head[MAXN],num_edge;
 17 struct node1
 18 {
 19     LL val;
 20     LL add;
 21 } Segt[MAXN*4];
 22 struct node2
 23 {
 24     LL to;
 25     LL next;
 26 } edge[MAXN*2];
 27 void add(LL u,LL v)
 28 {
 29     edge[++num_edge].to=v;
 30     edge[num_edge].next=head[u];
 31     head[u]=num_edge;
 32 }
 33 
 34 void Dfs1(LL x)
 35 {
 36     Sum[x]=1;
 37     Depth[x]=Depth[Father[x]]+1;
 38     for (LL i=head[x]; i!=0; i=edge[i].next)
 39         if (edge[i].to!=Father[x])
 40         {
 41             Father[edge[i].to]=x;
 42             Dfs1(edge[i].to);
 43             Sum[x]+=Sum[edge[i].to];
 44             if (Son[x]==0 || (Sum[Son[x]]<Sum[edge[i].to]))
 45                 Son[x]=edge[i].to;
 46         }
 47 }
 48 
 49 void Dfs2(LL x,LL tp)
 50 {
 51     T_num[x]=++sum;
 52     Tree[sum]=a[x];
 53     Top[x]=tp;
 54     if (Son[x])
 55         Dfs2(Son[x],tp);
 56     for (LL i=head[x]; i!=0; i=edge[i].next)
 57         if (edge[i].to!=Son[x] && edge[i].to!=Father[x])
 58             Dfs2(edge[i].to,edge[i].to);
 59 }
 60 
 61 void Pushdown(LL node,LL l,LL r)
 62 {
 63     if (Segt[node].add!=0)
 64     {
 65         LL mid=(l+r)/2;
 66         Segt[node*2].val+=Segt[node].add*(mid-l+1);
 67         Segt[node*2+1].val+=Segt[node].add*(r-mid);
 68         Segt[node*2].add+=Segt[node].add;
 69         Segt[node*2+1].add+=Segt[node].add;
 70         Segt[node].add=0;
 71     }
 72 }
 73 
 74 void Build(LL node,LL l,LL r)
 75 {
 76     if (l==r)
 77         Segt[node].val=Tree[l];
 78     else
 79     {
 80         LL mid=(l+r)/2;
 81         Build(node*2,l,mid);
 82         Build(node*2+1,mid+1,r);
 83         Segt[node].val=Segt[node*2].val+Segt[node*2+1].val;
 84     }
 85 }
 86 
 87 void Update(LL node,LL l,LL r,LL l1,LL r1,LL k)
 88 {
 89     if (l>r1 || r<l1)
 90         return;
 91     if (l1<=l && r<=r1)
 92     {
 93         Segt[node].val+=(r-l+1)*k;
 94         Segt[node].add+=k;
 95         return;
 96     }
 97     Pushdown(node,l,r);
 98     LL mid=(l+r)/2;
 99     Update(node*2,l,mid,l1,r1,k);
100     Update(node*2+1,mid+1,r,l1,r1,k);
101     Segt[node].val=Segt[node*2].val+Segt[node*2+1].val;
102 }
103 
104 LL Query(LL node,LL l,LL r,LL l1,LL r1)
105 {
106     if (l>r1 || r<l1)
107         return 0;
108     if (l1<=l && r<=r1)
109         return Segt[node].val;
110     Pushdown(node,l,r);
111     LL mid=(l+r)/2;
112     return Query(node*2,l,mid,l1,r1)+Query(node*2+1,mid+1,r,l1,r1);
113 }
114 
115 LL Get(LL x)
116 {
117     LL ans=0;
118     while (x!=0)
119     {
120         ans+=Query(1,1,n,T_num[Top[x]],T_num[x]);
121         x=Father[Top[x]];
122     }
123     return ans;
124 }
125 
126 int main()
127 {
128     scanf("%lld%lld",&n,&m);
129     for (LL i=1; i<=n; ++i)
130         scanf("%lld",&a[i]);
131     for (LL i=1; i<=n-1; ++i)
132     {
133         scanf("%lld%lld",&u,&v);
134         add(u,v);
135         add(v,u);
136     }
137     Dfs1(1);
138     Dfs2(1,1);
139     Build(1,1,n);
140     for (LL i=1; i<=m; ++i)
141     {
142         LL p,x,y;
143         scanf("%lld",&p);
144         if (p==1)
145         {
146             scanf("%lld%lld",&x,&y);
147             Update(1,1,n,T_num[x],T_num[x],y);
148         }
149         if (p==2)
150         {
151             scanf("%lld%lld",&x,&y);
152             Update(1,1,n,T_num[x],T_num[x]+Sum[x]-1,y);
153         }
154         if (p==3)
155         {
156             scanf("%lld",&x);
157             printf("%lld
",Get(x));
158         }
159     }
160 }