这是一道树链剖分的水题..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[100005];
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
const int maxn=100005;
int depth[maxn];
int size[maxn];
int father[maxn];
int up[maxn];
edge * prefer_edge[maxn];
void dfs1(int x)
{
    edge * t;
    size[x]=1;
    int max_size=0;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        depth[t->y]=depth[x]+1;
        father[t->y]=x;
        dfs1(t->y);
        size[x]+=size[t->y];
        if (max_size<size[t->y])
        {
            max_size=size[t->y];
            prefer_edge[x]=t;
        }
    }
}
int vis[maxn];
int dfn[maxn];
void dfs2(int x)
{
    static int num=0;
    dfn[x]=num;
    vis[num]=x;
    num++;
    if (prefer_edge[x]==0) return;
    up[prefer_edge[x]->y]=up[x];
    dfs2(prefer_edge[x]->y);
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (t->y==father[x]) continue;
        if (t==prefer_edge[x]) continue;
        up[t->y]=t->y;
        dfs2(t->y);
    }
}
long long val[1<<18];
long long tag[1<<18];
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=a[vis[l]];
        tag[num]=0;
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    tag[num]=0;
    val[num]=val[num*2+1]+val[num*2+2];
}
void change(int num,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        val[num]+=(long long)k*(r-l);
        tag[num]+=k;
        return;
    }
    int mid=(l+r)/2;
    if (l0<mid) change(num*2+1,l,mid,l0,r0,k);
    if (mid<r0) change(num*2+2,mid,r,l0,r0,k);
    val[num]=val[num*2+1]+val[num*2+2]+(r-l)*tag[num];
}
long long query(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    long long sum=0;
    if (l0<mid) sum+=query(num*2+1,l,mid,l0,r0)+tag[num]*(min(r0,mid)-max(l,l0));
    if (mid<r0) sum+=query(num*2+2,mid,r,l0,r0)+tag[num]*(min(r0,r)-max(mid,l0));
    return sum;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    father[0]=-1;
    up[0]=0;
    depth[0]=0;
    dfs1(0);
    dfs2(0);
    build_tree(0,0,n);
    for (i=0;i<m;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            change(0,0,n,dfn[x],dfn[x]+1,y);
        }
        else if (oper==2)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            change(0,0,n,dfn[x],dfn[x]+size[x],y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            x--;
            long long ans=0;
            for (;;)
            {
                ans+=query(0,0,n,dfn[up[x]],dfn[x]+1);
                x=father[up[x]];
                if (x==-1) break;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}