大概树链剖分裸题吧(没开ll  WA了两发

4034: [HAOI2015]树上操作

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 6360  Solved: 2109

[][][]

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

#include 
      
       #define N 100005#define ll long longusing namespace std;int son[N],num[N],dep[N],fa[N];int cnt,p[N],fp[N],tp[N],a[N],n,m;vector
       
        vec[N];int read(){    int x=0,f=1;char ch=getchar();    while(!isdigit(ch)){
    if(ch=='-')f=-1;ch=getchar();}    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return f*x;}void dfs1(int v,int pre,int deep){    num[v]=1;fa[v]=pre;dep[v]=deep+1;    for(int i=0;i
        
         >1;    built(root<<1,l,mid);    built(root<<1|1,mid+1,r);    d[root].l=d[root<<1].l;d[root].r=d[root<<1|1].r;d[root].flag=0;    up(root);}void update(int root,int l,int r,int t){    if(l<=d[root].l&&d[root].r<=r){        update_add(root,t);        return ;    }    push(root);    int mid=(d[root].l+d[root].r)>>1;    if(l<=mid) update(root<<1,l,r,t);    if(r>mid) update(root<<1|1,l,r,t);    up(root);}ll ans1;void querty(int root,int l,int r){    if(l<=d[root].l&&d[root].r<=r){        ans1+=d[root].sum;        return ;    }    int mid=(d[root].l+d[root].r)>>1;    push(root);    if(l<=mid) querty(root<<1,l,r);    if(r>mid) querty(root<<1|1,l,r);    up(root);}ll Sum(int v){    ll ans=0;int vv=tp[v];    while(tp[v]!=1){        ans1=0;querty(1,p[vv],p[v]);        ans+=ans1;        v=fa[vv];vv=tp[v];    }    ans1=0;querty(1,1,p[v]);    ans+=ans1;    return ans;}int main(){    ios::sync_with_stdio(false);    n=read();m=read();cnt=0;    for(int i=1;i<=n;i++) a[i]=read();    for(int i=1;i<=n;i++) son[i]=-1;    int t1,t2,op;    for(int i=1;i