[haoi2015] tree operation

[HAOI2015] Tree operation ( Read notes )

Title Description

There's a tree that counts N The tree of , With a little 1 Root , And the tree point has edge weight . Then there is M Operations , Divided into three ：

• operation 1 ： Take a node x The point weight of a .
• operation 2 ： Take a node x Increase the weight of all points in the subtree of the root a .
• operation 3 ： Ask a node x The sum of the point weights of all points in the path to the root .

Input format

The first line contains two integers N, M . Represents the number of points and operands .
Next line N It's an integer , Represents the initial weights of the nodes in the tree .
Next N-1 Two positive integers per line from, to , Indicates that there is an edge in the tree (from, to) .
Next M That's ok , Each line represents an operation . The first number indicates the type of operation （ 1-3 ） , And then the parameters of this operation （ x perhaps x a ） .

Output format

For each query operation , Output the answer to the question . The answers are separated by newlines .

Examples #1

The sample input #1

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 #1

6
9
13

Tips

about 100% The data of , N,M<=100000 , And the absolute value of all input data will not exceed 10^6 .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int head[N],cnt;
int fa[N],size[N],deep[N],son[N],top[N],dfsxu[N],id[N],k;
//fa[i]  node i Parent node  size[i]  With i Is the total number of nodes in the subtree of the root 
//deep[i]  node i The depth of the  son[i]  node i My dear son 
//top[i]  node i The top element of the heavy chain 
//dfsxu  Initial value of each point  id  Time stamp 
//dfs Order can reflect the continuous information of points on the tree , The chain is dfs order 
int n,v[N],m,r,ss[N];
struct stu{
    
    int l,r,sum,lz;
}tree[N*4];
struct stuu{
    
	int to,nt;
}ed[N*2];
void add(int u,int v){
    // Chain forward star edge 
	ed[cnt]=stuu{
    v,head[u]};
	head[u]=cnt++;
}
void dfs1(int u,int f){
    //u Is the current node ,f Is the parent node of the current node ; initialization 1
    fa[u]=f;//u The parent of the node is f
    deep[u]=deep[f]+1;// depth +1
    size[u]=1;
    int maxsize=-1;// It is a temporary variable to judge whether it is a heavy son 
    for(int i=head[u];i!=-1;i=ed[i].nt){
    // Traverse all the sons , Keep updating and find your son 
		int v=ed[i].to;
        if(v==f) continue;// My father must have skipped it directly 
        dfs1(v,u);// Depth traversal , The current node becomes the parent node , The found son becomes the current node and continues to traverse 
        size[u]+=size[v];// After traversal , Let the size of the current node plus the size of the son 
        if(size[v]>maxsize){
    // If the size of the son is larger than the temporary variable 
            maxsize=size[v];// Just assign it to a temporary variable 
            son[u]=v;// Change the heavy son of the current node 
        }
    }
}
void dfs2(int u,int t){
    // initialization 2
    id[u]=++k;// Each node is timestamped 
    top[u]=t;// node u The top of the heavy chain is t
    dfsxu[k]=ss[u];// Save dfs order 
    if(!son[u]) return;// If there is no heavy son, there will be no son. Go back directly 
    dfs2(son[u],t);// Continue to walk towards your son 
    for(int i=head[u];i!=-1;i=ed[i].nt){
    
        int v =ed[i].to;
        if(v==fa[u]||v==son[u]) continue;// If it is a parent node or a duplicate son, skip directly 
        dfs2(v,v);// Some heavy chains start with light sons and go down , The top is light son 
    }
}
void pushup(int u){
    // Update up 
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;// The interval sum of the left and right sub segments is fed back to the top 
}
void pushdown(int u){
    // Update down , take lazy Mark push down 
    if(tree[u].lz){
    
        tree[u<<1].sum+=tree[u].lz*(tree[u<<1].r-tree[u<<1].l+1);
        tree[u<<1|1].sum+=tree[u].lz*(tree[u<<1|1].r-tree[u<<1|1].l+1);
        tree[u<<1].lz+=tree[u].lz;
        tree[u<<1|1].lz+=tree[u].lz;
        tree[u].lz=0;
    }
}
void build(int l,int r,int u){
    // Build up trees 
    tree[u].l=l,tree[u].r=r;
	if(l==r){
    // Reach the leaf node , Update and return 
        tree[u].sum=dfsxu[l];
		return ;
	}// Otherwise, this node represents more than one point , It also has two sons 
	int mid=(l+r)>>1;
	build(l,mid,u<<1);// Recursive left subtree 
	build(mid+1,r,u<<1|1);// Recursive right subtree 
	pushup(u);// to update 
}
void update(int l,int r,int u,int b){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    // Included as a subinterval , Then make an overall modification , Don't go further 
        tree[u].sum+=b*(tree[u].r-tree[u].l+1);
        tree[u].lz+=b;
        return ;
    }// Otherwise, it is staggered , You need to continue to go deeper into the lower sub interval 
    pushdown(u);// Update down 
    int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid) update(l,r,u<<1,b);// Recursive left subtree 
	if(r>=mid+1) update(l,r,u<<1|1,b);// Recursive right subtree 
	pushup(u);// to update 
}
int query(int l,int r,int u){
    
    if(l<=tree[u].l&&tree[u].r<=r){
    // Included as a subinterval , Then make an overall modification , Don't go further 
        return tree[u].sum;
    }// Otherwise, it is staggered , You need to continue to go deeper into the lower sub interval 
    int k=0;
	int mid=(tree[u].l+tree[u].r)>>1;// Binary search 
    pushdown(u);// Update down 
	if(l<=mid) k+=query(l,r,u<<1);// Part of the inquiry is under the jurisdiction of the left son 
	if(r>=mid+1) k+=query(l,r,u<<1|1);// Part of it is within the scope of the right son 
	return k;
}
int querycc(int a,int b){
    
    int k=0;
    while(top[a]!=top[b]){
    // look for LCA： When x,y Not in the same heavy chain , Compare x,y The depth of the head of the heavy chain 
        if(deep[top[a]]<deep[top[b]]) swap(a,b);// Ensure deeper 
        k+=query(id[top[a]],id[a],1);// By climbing lca Every time you jump the chain head to modify or query the interval 
        a=fa[top[a]];// The deeper one jumps along the heavy chain to the father at the head of the chain 
    }
    if(deep[a]>deep[b]) swap(a,b);// It can be operated directly on a heavy chain 
    k+=query(id[a],id[b],1);
    return k;
}
signed main(){
    
    int x,y,z;
	memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&ss[i]);
    for(int i=1;i<n;i++){
    
        scanf("%lld%lld",&x,&y);
        add(x,y),add(y,x);
    }
    dfs1(1,0),dfs2(1,1);
    build(1,n,1);
    while(m--){
    
        scanf("%lld",&z);
        if(z==1){
    
            scanf("%lld%lld",&x,&y);
            update(id[x],id[x],1,y);
        }
        else if(z==2){
    
            scanf("%lld%lld",&x,&y);
            update(id[x],id[x]+size[x]-1,1,y);
        }
        else if(z==3){
    
            scanf("%lld",&x);
            printf("%lld\n",querycc(x,1));
        }
    }
}