HDU 3966 Aragorn's Story

#include<cstdio>  
#include<algorithm>  
#include<iostream>  
#include<cstring>
using namespace std;
#define maxn 1000005 
int val[maxn];  
int u[maxn],to[maxn],head[maxn],nex[maxn];
int e_max;  
int deep[maxn],fa[maxn],top[maxn],son[maxn],siz[maxn],pos[maxn];  
int c[maxn];  
int tot=1;
void dfs1(int k,int pre,int d)  
{  
    fa[k]=pre;  
    deep[k]=d;  
    siz[k]++;  
    for(int i=head[k]; ~i; i=nex[i])  
    {  
        int e=to[i];  
        if(e!=pre)  
        {  
            dfs1(e,k,d+1);  
            if(son[k]==-1||siz[e]>siz[son[k]]) son[k]=e;  
            siz[k]+=siz[e];  
        }  
    }  
} 
void dfs2(int k,int sp)  
{  
    top[k]=sp;  
    pos[k]=tot++;  
    if(son[k]==-1) return ;  
    dfs2(son[k],sp);  
    for(int i=head[k]; ~i; i=nex[i])  
    {  
        if(to[i]!=fa[k]&&to[i]!=son[k])  
        {  
            dfs2(to[i],to[i]);  
        }  
    }  
}  
inline void add(int x,int y){
	++tot;
	to[tot]=y;
	nex[tot]=head[x];
	head[x]=tot;
}
int lowbit(int x)  
{  
    return x&-x;  
}  
void update(int x,int val)  
{  
    for(;x<=maxn;x+=lowbit(x)) c[x]+=val;  
}  
int query(int x)  
{  
    int sum=0;  
    for(; x>0; x-=lowbit(x)) sum+=c[x];  
    return sum;  
}  
void change(int s,int t,int c)  
{  
    int f1=top[s],f2=top[t];  
    while(f1!=f2)  
    {  
        if(deep[f1]<deep[f2]) swap(f1,f2),swap(s,t);  
        update(pos[f1],c);  
        update(pos[s]+1,-c);  
        s=fa[f1];  
        f1=top[s];  
    }  
    if(deep[s]>deep[t]) swap(s,t);  
    update(pos[s],c);  
    update(pos[t]+1,-c);  
}  
int main(){
	int n,m,q;
	 while(scanf("%d%d%d",&n,&m,&q)!=EOF)  
	 {
			memset(c,0,sizeof c);  
   		 	memset(siz,0,sizeof siz);  
   		 	memset(son,-1,sizeof son);  
    		memset(fa,-1,sizeof fa);  
    		memset(head,-1,sizeof head);  
    		e_max=0;  
    		for(int i=1;i<=n;i++) scanf("%d",&val[i]);
    		for(int i=0;i<m;i++)  
        	{  
            	int a,b;  
            	scanf("%d%d",&a,&b);  
            	add(a,b);  
            	add(b,a);  
        	}  
        	dfs1(1,1,1);
        	dfs2(1,1);
        	for(int i=1;i<=n;i++) update(pos[i],val[i]),update(pos[i]+1,-val[i]);
        	for(int i=1;i<=q;i++)
        	{
        		  char s[5];  
            	scanf("%s",s);  
            	if(s[0]=='Q')  
            	{  
                	int index;  
                	scanf("%d",&index);  
                	printf("%d\n",query(pos[index]));  
            	}  
            	else  
            	{  
               	 	int l,r,c;  
               		 scanf("%d%d%d",&l,&r,&c);  
                	if(s[0]=='D') c=-c;  
                	change(l,r,c);  
            	}  
        	}
	 }
	
	return 0;
}