题目描述

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

输入输出格式

输入格式：

 

输入文件的第一行为一个整数n，表示节点的个数。

接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来一行n个整数，第i个整数wi表示节点i的权值。

接下来1行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

 

输出格式：

 

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

 

输入输出样例

输入样例#1：

41 22 34 14 2 1 312QMAX 3 4QMAX 3 3QMAX 3 2QMAX 2 3QSUM 3 4QSUM 2 1CHANGE 1 5QMAX 3 4CHANGE 3 6QMAX 3 4QMAX 2 4QSUM 3 4

输出样例#1：

412210656516

说明

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

 

裸的树链剖分。

注意所有的值都要取最大或者最小。

有很小的负边权！

 

update：数据已加强，下面的代码现在不能通过!

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ls k<<1#define rs k<<1|1using namespace std;const int MAXN=1000001;inline void read(int &n){	char c='+';int x=0;bool flag=0;	while(c<'0'||c>'9')	{c=getchar();if(c=='-')flag=1;}	while(c>='0'&&c<='9')	{x=(x<<1)+(x<<3)+c-48,c=getchar();}	flag==1?n=-x:n=x;}int n;int a[MAXN];int fa[MAXN];// 每一个节点的父亲节点int deep[MAXN];// 每一个节点的深度int top[MAXN];// 重链上的顶节点int son[MAXN];// 每一个点的重儿子 int size[MAXN];// 子节点的数量int pos[MAXN];// 划分轻重链之后的编号int tot;// 总结点的数量 struct node{	int l,r,maxn,sum;}tree[MAXN];struct EDGE{	int u,v,nxt;}edge[MAXN];int head[MAXN];int num=1;//int nowmax=-1;int nowsum=0;void update(int k){	tree[k].maxn=max(tree[ls].maxn,tree[rs].maxn);	tree[k].sum=(tree[ls].sum+tree[rs].sum);}void add_edge(int x,int y){	edge[num].u=x;	edge[num].v=y;	edge[num].nxt=head[x];	head[x]=num++;}int dfs1(int now,int nowfa,int nowdeep){	deep[now]=nowdeep;	fa[now]=nowfa;	size[now]=1;	for(int i=head[now];i!=-1;i=edge[i].nxt)	{		if(edge[i].v!=nowfa)		{			dfs1(edge[i].v,now,nowdeep+1);			size[now]+=size[edge[i].v];			if(son[now]==-1||size[edge[i].v]>size[son[now]])				son[now]=edge[i].v;		}	}}void dfs2(int now,int nowid){	tot++;	pos[now]=tot;//更改当前节点的编号	top[now]=nowid;	if(!son[now])// 没有重儿子	 	return ;	dfs2(son[now],nowid);// 在一条重链上	for(int i=head[now];i!=-1;i=edge[i].nxt)		if(deep[edge[i].v]>deep[edge[i].u]&&edge[i].v!=son[edge[i].u])			dfs2(edge[i].v,edge[i].v);//自己和自己一条重链		return ; }void build_tree(int k,int ll,int rr){	tree[k].l=ll;tree[k].r=rr;	if(tree[k].l==tree[k].r)	{		tree[k].maxn=tree[k].sum=0;		return ;	}	int mid=(ll+rr)>>1;	build_tree(ls,ll,mid);	build_tree(rs,mid+1,rr);	update(k);}void insert(int k,int pos,int val){	if(tree[k].l==tree[k].r)	{		tree[k].maxn=tree[k].sum=val;		return ;	}	int mid=(tree[k].l+tree[k].r)>>1;	if(pos<=mid)		insert(ls,pos,val);	if(pos>mid)		insert(rs,pos,val);	update(k);	}int querymax(int k,int ll,int rr){	if(ll<=tree[k].l&&tree[k].r<=rr)		return tree[k].maxn;	int mid=(tree[k].l+tree[k].r)>>1,nowmax=-1;	if(ll<=mid)		nowmax=max(nowmax,querymax(ls,ll,rr));	if(rr>mid)		nowmax=max(nowmax,querymax(rs,ll,rr));	return nowmax;}int askmax(int u,int v){		int ans=-0x7ffff;	while(top[u]!=top[v])//不在一条重链上	{		if(deep[top[u]]
          
           pos[v]) swap(u,v); ans=max(ans,querymax(1,pos[u],pos[v])); return ans;}int querysum(int k,int ll,int rr){ if(ll<=tree[k].l&&tree[k].r<=rr) return tree[k].sum; int mid=(tree[k].l+tree[k].r)>>1,nowsum=0; if(ll<=mid) nowsum+=querysum(ls,ll,rr); if(rr>mid) nowsum+=querysum(rs,ll,rr); return nowsum;}int asksum(int u,int v){ int ans=0; while(top[u]!=top[v]) { if(deep[top[u]]
           
            pos[v]) swap(u,v); ans+=querysum(1,pos[u],pos[v]); return ans;}int main(){ ///freopen("bzoj_1036.in","r",stdin); //freopen("bzoj_1036.out","w",stdout); read(n); memset(head,-1,sizeof(head)); //memset(son,-1,sizeof(son)); for(int i=1;i<=n-1;i++) { int x,y; read(x);read(y); add_edge(x,y); add_edge(y,x); } for(int i=1;i<=n;i++) read(a[i]); dfs1(1,0,0); dfs2(1,1); build_tree(1,1,n); for(int i=1;i<=n;i++) insert(1,pos[i],a[i]); int q; read(q); for(int i=1;i<=q;i++) { string s; cin>>s; if(s[1]=='H')// 修改 { int p,v; read(p);read(v); a[p]=v; insert(1,pos[p],v); } else if(s[1]=='M')// 最大值 { int l,r; read(l);read(r); printf("%d\n",askmax(l,r)); } else//求和 { int l,r; read(l);read(r); printf("%d\n",asksum(l,r)); } } return 0;}