#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 50005
struct Edge{
int to,nxt;}edge[maxn<<
1];
int head[maxn],tot,n,m,q,v[maxn];
void init(){memset(head,-
1,
sizeof head);tot=
0;}
void addedge(
int u,
int v){edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++
;}
int f[maxn],size[maxn],d[maxn],son[maxn];
void dfs1(
int x,
int pre,
int deep){
size[x]=
1;d[x]=deep;f[x]=
pre;
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(y==pre)
continue;
dfs1(y,x,deep+
1);
size[x]+=
size[y];
if(size[y]>size[son[x]])son[x]=
y;
}
}
int top[maxn],id[maxn],rk[maxn],cnt;
void dfs2(
int x,
int tp){
top[x]=tp;id[x]=++cnt;rk[cnt]=
x;
if(son[x])dfs2(son[x],tp);
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(y!=son[x] && y!=
f[x])dfs2(y,y);
}
}
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int lazy[maxn<<
2];
void pushdown(
int rt){
if(lazy[rt]){
lazy[rt<<
1]+=lazy[rt];lazy[rt<<
1|
1]+=
lazy[rt];
lazy[rt]=
0;
}
}
void update(
int L,
int R,
int l,
int r,
int rt,
int c){
if(L<=l && R>=r){lazy[rt]+=c;
return;}
int m=l+r>>
1;
pushdown(rt);
if(L<=
m)update(L,R,lson,c);
if(R>
m)update(L,R,rson,c);
}
int query(
int pos,
int l,
int r,
int rt){
if(l==r)
return lazy[rt]+
v[rk[l]];
pushdown(rt);
int m=l+r>>
1;
if(pos<=m)
return query(pos,lson);
else return query(pos,rson);
}
void Update(
int x,
int y,
int c){
while(top[x]!=
top[y]){
if(d[top[x]]<
d[top[y]])swap(x,y);
update(id[top[x]],id[x],1,n,
1,c);
x=
f[top[x]];
}
if(id[x]>
id[y])swap(x,y);
update(id[x],id[y],1,n,
1,c);
}
int main(){
while(scanf(
"%d%d%d",&n,&m,&q)==
3){
init();int x,y,z;
char op[
2];
for(
int i=
1;i<=n;i++)scanf(
"%d",&
v[i]);
for(
int i=
1;i<n;i++){scanf(
"%d%d",&x,&
y);addedge(x,y);addedge(y,x);}
memset(son,0,
sizeof son);memset(f,
0,
sizeof f);
cnt=
0;dfs1(
1,
0,
1);dfs2(
1,
1);
memset(lazy,0,
sizeof lazy);
while(q--
){
scanf("%s",&
op);
if(op[
0]==
'I'){scanf(
"%d%d%d",&x,&y,&
z);Update(x,y,z);}
if(op[
0]==
'D'){scanf(
"%d%d%d",&x,&y,&z);Update(x,y,-
z);}
if(op[
0]==
'Q'){scanf(
"%d",&x);cout<<query(id[x],
1,n,
1)<<
'\n';}
}
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10755276.html
