记录编号	372350	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	1.366 s
提交时间	2017-02-18 11:32:38	内存使用	16.18 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ok 1,1,N
using namespace std;
 
const int maxn=30000+10;
 
struct edge
{
       int to,next;
}e[maxn*2];
 
int fa[maxn],data[maxn],sz[maxn],num[maxn],dfn[maxn],id[maxn],son[maxn],top[maxn],deep[maxn];
 
int head[maxn];
 
int ma[maxn*4],sum[maxn*4];
 
int N,Q,len,Cnt;
 
void ADD(int x,int y)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     head[x]=len;
}
 
void dfs1(int x)
{
     sz[x]=1;
     fa[x]=x;
     for(int t,i=head[x];i;i=e[i].next)
     {
           t=e[i].to;
           if(!sz[t])
           {
             deep[t]=deep[x]+1;
            dfs1(t);
            fa[t]=x;
            sz[x]+=sz[t];
            if(sz[t]>sz[son[x]])
            son[x]=t;
           }  
     }
}
 
void dfs2(int x,int tp)
{
     top[x]=tp;
     dfn[x]=++Cnt;
     id[Cnt]=x;
     if(son[x])dfs2(son[x],tp);
     for(int t,i=head[x];i;i=e[i].next)
     {
             t=e[i].to;
             if(!dfn[t])
             {
             dfs2(t,t);
             }
     }
}
 
 
void Build(int rt,int l,int r)
{
     if(l==r)
     {
       ma[rt]=data[id[l]];
       sum[rt]=data[id[l]];
       return;
     }
     int mid=(l+r)>>1;
     Build(lson);
     Build(rson);
     ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
 
int  qmax(int rt,int l,int r,int s,int t )
{
     if(s<=l&&t>=r)
     {
      return ma[rt];
     }
     int mid=(l+r)>>1;
     if(t<=mid)return qmax(lson,s,t);
     if(s>mid)return qmax(rson,s,t);
     return max(qmax(lson,s,t),qmax(rson,s,t));
}
 
void change(int rt,int l,int r,int s,int data)
{
     if(s<=l&&s>=r)
     {
        ma[rt]=data;
        sum[rt]=data;
        return;
     }
     int mid=(l+r)>>1;
     if(s<=mid)change(lson,s,data);
     else change(rson,s,data);
      ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
 
int  qsum(int rt,int l,int r,int s,int t )
{
     if(s<=l&&t>=r)
     {
      return sum[rt];
     }
     int mid=(l+r)>>1;
     if(t<=mid)return qsum(lson,s,t);
     if(s>mid)return qsum(rson,s,t);
     return (qsum(lson,s,t)+qsum(rson,s,t));
}
 
 
 
 
int Qmax(int x,int y)
{
    int Ans=-0x7ffffff;
    while(top[x]!=top[y])
    {
             if(deep[top[x]]<deep[top[y]])
             {
               swap(x,y);
             }           
             Ans=max(Ans,qmax(ok,dfn[top[x]],dfn[x]));         
             x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    Ans=max(Ans,qmax(ok,dfn[x],dfn[y]));
    return Ans;
}
 
int Qsum(int x,int y)
{
    int Ans=0;
    while(top[x]!=top[y])
    {
             if(deep[top[x]]<deep[top[y]])
             {
               swap(x,y);
             }
             Ans+=qsum(ok,dfn[top[x]],dfn[x]);         
             x=fa[top[x]];
    }
    if(deep[x]>deep[y])swap(x,y);
    Ans+=qsum(ok,dfn[x],dfn[y]);
    return Ans;
}
 
int main()
{
    
    freopen("bzoj_1036.in","r",stdin);
    freopen("bzoj_1036.out","w",stdout);
    scanf("%d",&N);
    for(int x,y,i=1;i<N;i++)
    {
        scanf("%d%d",&x,&y);
        ADD(x,y);ADD(y,x);    
    }
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<=N;i++)
    {
      scanf("%d",&data[i]);
    }
    Build(1,1,N);
    scanf("%d",&Q);
    char op[10];
    for(int x,y,i=1;i<=Q;i++)
    {
         scanf("%s",op);
         scanf("%d%d",&x,&y);
         
         if(op[1]=='M')
         {
           printf("%d\n",Qmax(x,y));            
         }
         if(op[1]=='S')
         {
         printf("%d\n",Qsum(x,y));          
         }
         if(op[1]=='H')
         {
              change(ok,dfn[x],y);         
         }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}