记录编号	167173	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	arksandom	是否通过	通过
代码语言	C++	运行时间	1.774 s
提交时间	2015-06-22 01:37:56	内存使用	33.88 MiB

/*HAOI2015 T2*/
/*裸树链剖分*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=400010;
int fa[maxn],son[maxn],top[maxn],loc[maxn],siz[maxn],mx[maxn],dfs_clock;
int n,m;
ll sum[maxn<<1],mark[maxn<<1],init[maxn];//线段树
vector<int> g[maxn];

void build()
{
    static int q[maxn],head,tail,cur[maxn],st[maxn],ptr;
    q[tail++]=1;
    while(head<tail){
        int x=q[head++];
        siz[x]=1;
        for(int i=0;i<g[x].size();i++){
            int& y=g[x][i];
            if(y==fa[x])continue;
            fa[y]=x;
            q[tail++]=y;
        }
    }
    for(int i=tail-1;i>=0;i--){
        int x=q[i];
        siz[fa[x]]+=siz[x];
        if(siz[x]>siz[son[fa[x]]])son[fa[x]]=x;
    }
    //for(int i=1;i<=n;i++)cout<<"node "<<i<<" "<<fa[i]<<" "<<siz[i]<<" "<<son[i]<<endl;
    //非递归
    st[++ptr]=1; top[1]=1; loc[1]=mx[1]=++dfs_clock;
    while(ptr){
        int now=st[ptr];
        if(!loc[now]){
            loc[now]=mx[now]=++dfs_clock;
        }
        if(cur[now]>=g[now].size())ptr--;
        else if(loc[now]==dfs_clock&&son[now]){
            top[son[now]]=top[now];
            st[++ptr]=son[now];
        }
        else
        for(int& i=cur[now];i<g[now].size();i++){
            int& y=g[now][i];
            if(y==fa[now]||y==son[now])continue;
            //if(y==son[now])top[y]=top[now];
            //else top[y]=y;
            top[y]=y;
            st[++ptr]=y;
            ++i;
            break;
        }
    }
    for(int i=tail-1;i>=0;i--){
        int x=q[i];
        mx[fa[x]]=max(mx[fa[x]],mx[x]);
    }
    //for(int i=1;i<=n;i++)cout<<loc[i]<<" ";cout<<endl;
}
/*
void dfs1(int x)
{
    siz[x]=1; son[x]=0;
    for(int i=0;i<g[x].size();i++){
        int& y=g[x][i];
        if(y==fa[x])continue;
        fa[y]=x;
        dfs1(y);
        if(siz[y]>siz[son[x]])son[x]=y;
        siz[x]+=siz[y];
    }
}

void dfs2(int x,int tp)
{
    loc[x]=++dfs_clock; top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int i=0;i<g[x].size();i++){
        int& y=g[x][i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
*/
void putdown(int o,int l,int r)
{
    int m=(l+r)>>1;
    sum[o<<1]+=mark[o]*(m-l+1); sum[o<<1|1]+=mark[o]*(r-m);
    mark[o<<1]+=mark[o]; mark[o<<1|1]+=mark[o];
    mark[o]=0;
}

void modify(int o,int l,int r,int a,int b,ll k)//qujian jiak
{
    if(a<=l && r<=b){sum[o]+=k*(r-l+1); mark[o]+=k;}
    else{
        if(mark[o])putdown(o,l,r);
        int m=(l+r)>>1;
        if(a<=m)modify(o<<1,l,m,a,b,k);
        if(b>m)modify(o<<1|1,m+1,r,a,b,k);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
}

ll getsum(int o,int l,int r,int a,int b)
{
    if(a<=l && r<=b)return sum[o];
    if(mark[o])putdown(o,l,r);
    int m=(l+r)>>1;
    ll ans=0;
    if(a<=m)ans+=getsum(o<<1,l,m,a,b);
    if(b>m)ans+=getsum(o<<1|1,m+1,r,a,b);
    return ans;
}

ll query(int x)//询问x到1号节点的链和
{
    ll ans=0;
    for(int p=top[x];x;){
        ans+=getsum(1,1,n,loc[p],loc[x]);
        x=fa[p]; p=top[x];
    }
    return ans;
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("my.out","w",stdout);
    freopen("haoi2015_t2.in","r",stdin);
    freopen("haoi2015_t2.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%lld",&init[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y); g[y].push_back(x);
    }
    build();
    for(int i=1;i<=n;i++)modify(1,1,n,loc[i],loc[i],init[i]);
    for(int i=1;i<=m;i++){
        int opt,x;
        ll a;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%lld",&x,&a);
            modify(1,1,n,loc[x],loc[x],a);
        }
        else if(opt==2){
            scanf("%d%lld",&x,&a);
            modify(1,1,n,loc[x],loc[x]+siz[x]-1,a);
        }
        else{
            scanf("%d",&x);
            printf("%lld\n",query(x));
        }
    }
    return 0;
}