solution-code4581

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define fpos fpos2333
6
using namespace std;
7
struct Node
8
{
9
  int to,next;
10
}e[200005];
11
struct tree
12
{
13
  int L,R;
14
  long long lazy,sum;
15
}T[400005];
16
int a[200005],pos[200005],fpos[200005],top[200005],siz[200005],d[200005],pre[200005],h[200005],vson[200005],sign,cnt;
17
inline void Addedge(int x,int y)
18
{
19
  e[++cnt]=(Node){y,h[x]};h[x]=cnt;return;
20
}
21
inline void dfs1(int x,int prt,int dep)
22
{
23
  int i,y;
24
  d[x]=dep;siz[x]=1;
25
  pre[x]=prt;vson[x]=-1;
26
  for(i=h[x];i;i=e[i].next)
27
  {
28
    y=e[i].to;
29
    if(y==prt)continue;
30
    dfs1(y,x,dep+1);
31
    siz[x]+=siz[y];
32
    if(vson[x]==-1||siz[vson[x]]<siz[y])vson[x]=y;
33
  }
34
  return;
35
}
36
inline void dfs2(int x,int sp)
37
{
38
  int i,y;
39
  pos[x]=++sign;top[x]=sp;
40
  fpos[sign]=x;//!!!!!!!!
41
  if(vson[x]!=-1)dfs2(vson[x],sp);
42
  for(i=h[x];i;i=e[i].next)
43
  {
44
    y=e[i].to;
45
    if(y==vson[x]||y==pre[x])continue;
46
    dfs2(y,y);
47
  }
48
  return;
49
}
50
inline void pushup(int v)
51
{
52
  T[v].sum=T[v<<1].sum+T[(v<<1)|1].sum;
53
  return;
54
}
55
inline void pushdown(int v)
56
{
57
  if(!T[v].lazy)return;
58
  T[v<<1].sum+=1LL*(T[v<<1].R-T[v<<1].L+1)*T[v].lazy;
59
  T[(v<<1)|1].sum+=1LL*(T[(v<<1)|1].R-T[(v<<1)|1].L+1)*T[v].lazy;
60
  T[v<<1].lazy+=T[v].lazy;
61
  T[(v<<1)|1].lazy+=T[v].lazy;
62
  T[v].lazy=0;
63
  return;
64
}
65
inline void Build(int L,int R,int v)
66
{
67
  T[v].L=L;T[v].R=R;
68
  if(L==R)
69
  {
70
    T[v].sum=a[fpos[L]];
71
    return;
72
  }
73
  int mid=(L+R)>>1;
74
  Build(L,mid,v<<1);
75
  Build(mid+1,R,(v<<1)|1);
76
  pushup(v);
77
  return;
78
}
79
inline void Insert(int L,int R,int val,int v)
80
{
81
  if(L>T[v].R||R<T[v].L)return;
82
  if(L<=T[v].L&&R>=T[v].R)
83
  {
84
    T[v].sum+=1LL*(T[v].R-T[v].L+1)*val;
85
    T[v].lazy+=val;
86
    return;
87
  }
88
  pushdown(v);
89
  Insert(L,R,val,v<<1);
90
  Insert(L,R,val,(v<<1)|1);
91
  pushup(v);
92
  return;
93
}
94
inline long long Query(int L,int R,int v)
95
{
96
  if(L>T[v].R||R<T[v].L)return 0;
97
  if(L<=T[v].L&&R>=T[v].R)return T[v].sum;
98
  pushdown(v);
99
  return Query(L,R,v<<1)+Query(L,R,(v<<1)|1);
100
}
101
inline long long Query(int x,int y)
102
{
103
  long long sum=0;
104
  while(top[x]!=top[y])
105
  {
106
    if(d[top[x]]<d[top[y]])swap(x,y);
107
    sum+=Query(pos[top[x]],pos[x],1);
108
    x=pre[top[x]];
109
  }
110
  if(d[x]>d[y])swap(x,y);
111
  sum+=Query(pos[x],pos[y],1);
112
  return sum;
113
}
114
int main(void)
115
{
116
  int i,x,y,n,m,cmd;
117
  scanf("%d%d",&n,&m);
118
  for(i=1;i<=n;++i)scanf("%d",&a[i]);
119
  for(i=1;i<n;++i)
120
  {
121
    scanf("%d%d",&x,&y);
122
    Addedge(x,y);
123
    Addedge(y,x);
124
  }
125
  dfs1(1,1,1);
126
  dfs2(1,1);
127
  Build(1,sign,1);
128
  for(i=1;i<=m;++i)
129
  {
130
    scanf("%d%d",&cmd,&x);
131
    if(cmd==1)
132
    {
133
      scanf("%d",&y);
134
      Insert(pos[x],pos[x],y,1);
135
    }
136
    else if(cmd==2)
137
    {
138
      scanf("%d",&y);
139
      Insert(pos[x],pos[x]+siz[x]-1,y,1);
140
    }
141
    else printf("%lld\n",Query(1,x));
142
  }
143
  return 0;
144
}