[HAOI2015]树上操作

题目描述

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

输入输出格式

输入格式：

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 行每行三个正整数 fr, to ，表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

6
9
13

说明

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。

树链剖分。

代码实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ls k*2
 4 #define rs k*2+1
 5 #define LL long long
 6 #define maxn 100010
 7 using namespace std;
 8 LL a,b,c,ans;
 9 LL n,m,l,hs,nl;
10 LL s[maxn],h[maxn];
11 LL k[maxn],f[maxn],d[maxn],p[maxn],sz[maxn],is[maxn],ct[maxn];
12 struct node{LL s,n;}e[maxn<<1];
13 struct tree{LL l,r,s,f;}t[maxn<<2];
14 inline void add(LL x,LL y){e[++hs]=(node){y,h[x]};h[x]=hs;}
15 void dfs1(LL x,LL y,LL st){
16     f[x]=y;d[x]=st;sz[x]=1;
17     for(LL i=h[x];i;i=e[i].n)
18     if(e[i].s!=y){
19         dfs1(e[i].s,x,st+1);
20         sz[x]+=sz[e[i].s];
21         if(sz[e[i].s]>sz[is[x]]) is[x]=e[i].s;
22     }
23 }
24 void dfs2(LL x){
25     s[++l]=k[x];p[x]=l;
26     if(is[x]){
27         ct[is[x]]=ct[x];
28         dfs2(is[x]);
29     }
30     for(LL i=h[x];i;i=e[i].n)
31     if(e[i].s!=f[x]&&e[i].s!=is[x]){
32         ct[e[i].s]=e[i].s;
33         dfs2(e[i].s);
34     }
35 }
36 void build(LL k,LL l,LL r){
37     t[k].l=l;t[k].r=r;
38     if(l==r){t[k].s=s[++nl];return;}
39     LL mid=(l+r)>>1;
40     build(ls,l,mid);
41     build(rs,mid+1,r);
42     t[k].s=t[ls].s+t[rs].s;
43 }
44 void heritage(LL k){
45     t[ls].s+=(t[ls].r-t[ls].l+1)*t[k].f,t[ls].f+=t[k].f;
46     t[rs].s+=(t[rs].r-t[rs].l+1)*t[k].f,t[rs].f+=t[k].f;
47     t[k].f=0;
48 }
49 void change(LL k,LL l,LL r,LL al,LL ar,LL am){
50     if(l==al&&r==ar){t[k].f+=am,t[k].s+=(r-l+1)*am;return;}
51     if(t[k].f) heritage(k);
52     LL mid=(l+r)>>1;
53     if(al<=mid) change(ls,t[ls].l,t[ls].r,al,min(ar,mid),am);
54     if(ar>mid) change(rs,t[rs].l,t[rs].r,max(al,mid+1),ar,am);
55     t[k].s=t[ls].s+t[rs].s;
56 }
57 LL query(LL k,LL l,LL r,LL al,LL ar){
58     if(l==al&&r==ar) return t[k].s;
59     if(t[k].f) heritage(k);
60     LL mid=(l+r)>>1,ans=0;
61     if(al<=mid) ans+=query(ls,t[ls].l,t[ls].r,al,min(ar,mid));
62     if(ar>mid) ans+=query(rs,t[rs].l,t[rs].r,max(al,mid+1),ar);
63     return ans;
64 }
65 int main(){
66     scanf("%lld%lld",&n,&m);
67     for(LL i=1;i<=n;i++) scanf("%lld",&k[i]);
68     for(LL i=1;i<n;i++){scanf("%lld%lld",&a,&b);add(a,b);add(b,a);}
69     dfs1(1,0,1);
70     ct[1]=1;
71     dfs2(1);
72     build(1,1,l);
73     while(m--){
74         scanf("%lld%lld",&a,&b);
75         if(a==1){
76             scanf("%lld",&c);
77             change(1,1,l,p[b],p[b],c);
78             
79         }
80         if(a==2){
81             scanf("%lld",&c);
82             change(1,1,l,p[b],p[b]+sz[b]-1,c);
83         }
84         if(a==3){
85             ans=0;
86             for(;b;b=f[ct[b]])
87             ans+=query(1,1,l,p[ct[b]],p[b]);
88             printf("%lld
",ans);
89         }
90     }
91     return 0;
92 }

题目来源：洛谷