没过样例

#include <iostream>
#define int long long
using namespace std;
const int kMaxN=100001;
struct SLPF
{
  int heavyson,deep,size,top,father,newid;
}s[kMaxN*2];
struct XDS
{
  int l,r;
  int val,add;
}tr[kMaxN*4];
struct EDGE
{
  int to,nt;
}e[kMaxN*2];
int cnt,hd[kMaxN];
int n,m;
int a[kMaxN],b[kMaxN],num;
void Build(int where,int l,int r)
{
  tr[where].l=l;
  tr[where].r=r;
  if(l==r)
  {
    tr[where].val=b[l];
    return;
  }
  int mid=(l+r)/2;
  Build(where*2,l,mid);
  Build(where*2+1,mid+1,r);
  tr[where].val=tr[where*2].val+tr[where*2+1].val;
}
void Solve(int where)
{
  tr[where*2].val+=tr[where].add*(tr[where*2].r-tr[where*2].l+1);
  tr[where*2+1].val+=tr[where].add*(tr[where*2+1].r-tr[where*2+1].l+1);
  tr[where*2].add+=tr[where].add;
  tr[where*2+1].add+=tr[where].add;
  tr[where].add=0;
}
void Update(int where,int l,int r,int k)
{
  if(tr[where].l>=l&&tr[where].r<=r)
  {
    tr[where].val+=k*(tr[where].r-tr[where].l+1);
    tr[where].add+=k;
    return;
  }
  Solve(where);
  int mid=(tr[where].l+tr[where].r)/2;
  if(mid>=l)
  {
    Update(where*2,l,r,k);
  }
  if(mid<r)
  {
    Update(where*2+1,l,r,k);
  }
  tr[where].val=tr[where*2].val+tr[where*2+1].val;
}
int GetSum(int where,int l,int r)
{
  if(tr[where].l>=l&&tr[where].r<=r)
  {
    return tr[where].val;
  }
  Solve(where);
  int mid=(tr[where].l+tr[where].r)/2,sum=0;
  if(mid>=l)
  {
    sum+=GetSum(where*2,l,r);
  }
  if(mid<r)
  {
    sum+=GetSum(where*2+1,l,r);
  }
  return sum;
}
void Add(int a,int b)
{
  e[++cnt].to=b;
  e[cnt].nt=hd[a];
  hd[a]=cnt;
}
void dfs1(int now,int last)
{
  s[now].deep=s[last].deep+1;
  s[now].father=last;
  s[now].size=1;
  int maxson=0;
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==last)continue;
    dfs1(e[i].to,now);
    s[now].size+=s[e[i].to].size;
    if(s[e[i].to].size>maxson)
    {
      maxson=s[e[i].to].size;
      s[now].heavyson=e[i].to;
    }
  }
}
void dfs2(int now,int top)
{
  s[now].top=top;
  s[now].newid=++num;
  b[num]=a[now];
  if(s[now].heavyson==0)return;
  dfs2(s[now].heavyson,top);
  for(int i=hd[now];i;i=e[i].nt)
  {
    if(e[i].to==s[now].heavyson||e[i].to==s[now].father)continue;
    dfs2(e[i].to,e[i].to);
  }
}
int GetAns(int x,int y)
{
  int ans=0;
  while(s[x].top!=s[y].top)
  {
    if(s[s[x].top].deep<s[s[y].top].deep)
    {
      swap(x,y);
    }
    ans+=GetSum(1,s[s[x].top].newid,s[x].newid);
    x=s[s[x].top].father;
  }
  if(s[x].deep>s[y].deep)
  {
    swap(x,y);
  }
  ans+=GetSum(1,s[x].newid,s[y].newid);
  return ans;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
  cin>>a[i];
}
for(int i=1;i<n;i++)
{
  int a,b;
  cin>>a>>b;
  Add(a,b);
  Add(b,a);
}
dfs1(1,0);
dfs2(1,1);
Build(1,1,n);
while(m--)
{
  int op;
  cin>>op;
  if(op==1)
  {
    int x,a;
    cin>>x>>a;
    Update(1,s[x].newid,s[x].newid,a);
  }
  else if(op==2)
  {
    int x,a;
    cin>>x>>a;
    Update(1,s[x].newid,s[x].newid+s[x].size-1,a);
  }
  else
  {
    int x;
    cin>>x;
    cout<<GetAns(s[1].newid,s[x].newid)<<"\n";
  }
}
return 0;
}