hdu 3966 가장 순결 한 나무 사슬 분할

//	hdu 3966          
	
//	         。          ，  
//	    ，               ，  
//	  yy    ，         。      
//	       ，    ，       ，  
//	             ，   ，     
//	  ，         。     ，      
//	    。


#include 
#include 
#include 
#include 
#define cls(x,a) memset(x,(a),sizeof(x))
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int maxn = 50000 + 8;
int n,m,p;
int a[maxn];

int num;
int head[maxn];
struct edge{
	int to;
	int next;

	edge(){

	}
	edge(int to,int next):to(to),next(next){

	}

}edges[maxn<<1];


int id;
int dep[maxn]; //   
int father[maxn]; //    
int idx[maxn]; //            
int siz[maxn]; //              
int son[maxn]; //    
int top[maxn]; //   
int rk[maxn]; //  idx     ,              

void add_edges(int u,int v){
	edges[num] = edge(v,head[u]);
	head[u] = num++;
}

void dfs(int u,int fa,int d){
	dep[u] = d;
	father[u] = fa;
	siz[u] = 1;
	son[u] = 0;

	for(int i = head[u]; i != -1;i = edges[i].next){
		int v = edges[i].to;

		if (v == fa){
			continue;
		}
		dfs(v,u,d+1);
		siz[u] += siz[v];

		if (siz[son[u]] < siz[v])
			son[u] = v;
	}
	
}

void dfs(int u,int tp){
	top[u] = tp;
	idx[u] = id++;
	rk[idx[u]] = u;
	if (son[u])
		dfs(son[u],tp);

	for (int i = head[u];i!=-1;i = edges[i].next){
		int v = edges[i].to;

		if (v == father[u] || v == son[u])
			continue;

		dfs(v,v);
	}
}


//      

int seg[maxn<<2];
int laze[maxn<<2];
int ql,qr,delta;
void push_up(int ro){
	seg[ro] = seg[ro<<1] + seg[ro<<1|1];
}

void push_down(int ro,int m){
	if (laze[ro]){
		laze[ro<<1] += laze[ro]; 
		laze[ro<<1|1] += laze[ro];
		seg[ro<<1] += laze[ro] * (m - (m>>1));
		seg[ro<<1|1] += laze[ro] * (m>>1);
		laze[ro] = 0;
	}
}

void build(int ro,int L,int R){
	laze[ro] = 0;
	if (L == R){
		seg[ro] = a[rk[L]];
		return;
	}

	int M = (L + R) >> 1;

	build(ro<<1,L,M);
	build(ro<<1|1,M+1,R);
	push_up(ro);
}

void update(int ro,int L,int R){

	if (ql<=L && R<=qr){
		laze[ro] += delta;
		seg[ro] += (R-L+1) * delta;
		return ;
	}
	push_down(ro,R-L+1);
	int M = (L + R)>>1;

	if (ql <= M)	update(ro<<1,L,M);
	if (M < qr)	update(ro<<1|1,M+1,R);
	push_up(ro);
}

int query(int ro,int L,int R){

	if (L==R){
		return seg[ro];
	}
	
	push_down(ro,R-L+1);

	int M = (L + R) >> 1;

	if (ql <= M)	return query(ro<<1,L,M);
	else	return query(ro<<1|1,M+1,R);
	
}



void modify(int u,int v,int k){
	int p = top[u],q = top[v];

	while(p!=q){
		if (dep[p] < dep[q]){
			swap(p,q);
			swap(u,v);
		}
		ql = idx[p];
		qr = idx[u];
		delta = k;
		update(1,1,n);

		u = father[p];
		p = top[u];
	}

	if (dep[u] > dep[v])
		swap(u,v);

	ql = idx[u];
	qr = idx[v];
	delta = k;
	update(1,1,n);

}

void input(){
	cls(head,-1);
	cls(seg,0);
	cls(laze,0);
	num = 0;
	id = 1;
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add_edges(u,v);
		add_edges(v,u);
	}

	dfs(1,0,0);
	dfs(1,1);

	build(1,1,n);
	for (int i=1;i<=p;i++){
		char s[2];
		scanf("%s",s);
		if (s[0]=='Q'){
			int u;
			scanf("%d",&u);
			ql = idx[u];
			printf("%d
",query(1,1,n));
		}else if (s[0]=='I'){
			int a,b,k;
			scanf("%d%d%d",&a,&b,&k);
			modify(a,b,k);
		}else {
			int a,b,k;
			scanf("%d%d%d",&a,&b,&k);
			modify(a,b,-k);
		}
	}

}

int main(){
//	freopen("1.txt","r",stdin);
	while(scanf("%d%d%d",&n,&m,&p)!=EOF){
		input();
	}
	return 0;
}