#include <cstdio>
#include <cctype>
#include <cstdlib>
#define MAGIC 400
#define ROOT 1
#define BUF_SIZE 4096
#define MAXN 200000
#define MAXM 200000
long long aint[4*MAXN+1], tot[2*MAXN+1];
int *heap[MAXN+1], u[MAXN+1], val[2*MAXN-1], next[2*MAXN-1], lista[MAXN+1], st[MAXN+1], dr[MAXN+1], lin[MAXN+1], s[MAXN+1], sum[MAXN+1], tad[MAXN+1];
int fatfrumos[MAXN+1], special[MAXN+1], eu[MAXN+1], h[MAXN+1], hlant[MAXN+1], cati[MAXN+1], *nod[MAXN+1], tatic[MAXN+1], unde[MAXN+1], g[MAXN+1];
int e[MAXN+1], urm[MAXN+1], list[MAXN+1], v[MAXN+1];
long long ans;
int pos=BUF_SIZE, q, k, nr, w, n, cat, poz, left, right;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
if(pos==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fin);
pos=0;
}
return buf[pos++];
}
inline int read(){
int x=0, s=1;
char ch=nextch();
while((!isdigit(ch))&&(ch!='-')){
ch=nextch();
}
if(ch=='-'){
s=-1;
ch=nextch();
}
while(isdigit(ch)){
x=10*x+ch-'0';
ch=nextch();
}
return x*s;
}
void update(int p, int st, int dr){
if(st==dr){
aint[p]+=cat;
return ;
}
int m=(st+dr)/2;
if(poz<=m){
update(2*p, st, m);
}else{
update(2*p+1, m+1, dr);
}
aint[p]=aint[2*p]+aint[2*p+1];
}
void query(int p, int st, int dr){
if(p>4*MAXN){
printf("%d\n", p);
}
if((left<=st)&&(dr<=right)){
ans+=aint[p];
return ;
}
int m=(st+dr)/2;
if(left<=m){
query(2*p, st, m);
}
if(m+1<=right){
query(2*p+1, m+1, dr);
}
}
void dfsAint(int p, int st, int dr){
if(st==dr){
aint[p]=v[lin[st]];
return ;
}
int m=(st+dr)/2;
dfsAint(2*p, st, m);
dfsAint(2*p+1, m+1, dr);
aint[p]=aint[2*p]+aint[2*p+1];
}
inline int tata(int p){
return (p-1)/2;
}
inline int fiust(int p){
return 2*p+1;
}
inline int fiudr(int p){
return 2*p+2;
}
inline void swap(int heap[], int p, int q){
int aux=heap[p];
heap[p]=heap[q];
heap[q]=aux;
u[heap[p]]=p;
u[heap[q]]=q;
}
inline void urcare(int heap[], int p){
while((p>0)&&(tot[heap[p]]>tot[heap[tata(p)]])){
swap(heap, p, tata(p));
p=tata(p);
}
}
inline void coborare(int heap[], int p, int lim){
int q, f=1;
while((f)&&(fiust(p)<lim)){
q=fiust(p);
if((fiudr(p)<lim)&&(tot[heap[fiudr(p)]]>tot[heap[q]])){
q=fiudr(p);
}
if(tot[heap[q]]>tot[heap[p]]){
swap(heap, p, q);
p=q;
}else{
f=0;
}
}
}
inline void adauga(int x, int y){
q++;
val[q]=y;
next[q]=lista[x];
lista[x]=q;
}
void dfs(int x){
int p=lista[x];
eu[x]=n+x;
k++;
lin[k]=x;
st[x]=k;
s[x]=1;
sum[x]=0;
tot[x]=v[x];
fatfrumos[x]=0;
while(p){
if(val[p]!=tad[x]){
tad[val[p]]=x;
h[val[p]]=h[x]+1;
dfs(val[p]);
s[x]+=s[val[p]];
if(s[fatfrumos[x]]<s[val[p]]){
fatfrumos[x]=val[p];
}
tot[x]+=tot[val[p]];
sum[x]++;
}
p=next[p];
}
dr[x]=k;
if(sum[x]>=MAGIC){
special[x]=1;
heap[x]=(int*)malloc(sum[x]*sizeof(int));
for(int i=0, p=lista[x]; i<sum[x]; i++, p=next[p]){
if(val[p]==tad[x]){
p=next[p];
}
heap[x][i]=val[p];
u[val[p]]=i;
}
for(int i=tata(sum[x]-1); i>=0; i--){
coborare(heap[x], i, sum[x]);
}
}
if(fatfrumos[x]==0){
hlant[x]=h[x];
}else{
hlant[x]=hlant[fatfrumos[x]];
}
}
void hpd(int x){
int p, lant;
nr++;
lant=nr;
cati[lant]=hlant[x]-h[x]+1;
nod[lant]=(int*)malloc(cati[lant]*sizeof(int));
tatic[lant]=tad[x];
for(int i=0; i<cati[lant]; i++){
unde[x]=lant;
g[x]=i;
nod[lant][i]=x;
p=lista[x];
if(special[x]){
w++;
e[w]=x;
urm[w]=list[lant];
list[lant]=w;
}
while(p){
if((val[p]!=tad[x])&&(val[p]!=fatfrumos[x])){
hpd(val[p]);
}
p=next[p];
}
x=fatfrumos[x];
}
}
int main(){
int q, i, x, y, last, p;
long long sumtot, rasp;
char ch;
FILE *fout;
fin=fopen("rafaela.in", "r");
fout=fopen("rafaela.out", "w");
n=read();
q=read();
for(i=1; i<n; i++){
x=read();
y=read();
adauga(x, y);
adauga(y, x);
}
sumtot=0;
for(i=1; i<=n; i++){
v[i]=read();
sumtot+=v[i];
}
dfs(ROOT);
hpd(ROOT);
dfsAint(1, 1, n);
for(i=1; i<=n; i++){
if(st[i]>dr[i]){
return 1;
}
}
for(i=0; i<q; i++){
ch=nextch();
if(ch=='U'){
cat=read();
//sumtot+=cat;
x=read();
//poz=st[x];
//update(1, 1, n);
//last=0;
/*while(x!=0){
p=list[unde[x]];
while(p){
if(g[x]>g[e[p]]){
tot[nod[unde[x]][g[e[p]]+1]]+=cat;
urcare(heap[e[p]], u[nod[unde[x]][g[e[p]]+1]]);
tot[eu[e[p]]]+=cat;
}else if(g[x]==g[e[p]]){
tot[eu[e[p]]]+=cat;
if(last!=0){
tot[last]+=cat;
urcare(heap[e[p]], u[last]);
}
}
p=urm[p];
}
last=nod[unde[x]][0];
x=tatic[unde[x]];
}*/
}else{
x=read();
/*if(special[x]){
rasp=tot[heap[x][0]];
if(rasp<sumtot-tot[x]){
rasp=sumtot-tot[x];
}
fprintf(fout, "%lld\n", rasp);
}else{*/
ans=0;
left=st[x];
right=dr[x];
query(1, 1, n);
/*rasp=sumtot-ans;
p=lista[x];
while(p){
if(val[p]!=tad[x]){
ans=0;
left=st[val[p]];
right=dr[val[p]];
//query(1, 1, n);
if(ans>rasp){
rasp=ans;
}
}
p=next[p];
}*/
fprintf(fout, "%lld\n", rasp);
}
}
}
fclose(fin);
fclose(fout);
return 0;
}
Alexandru Petrescu
alexpetrescu
