一本通的一道题

样例都过不了

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
struct node{
	int maxson,top,size,fa,dep,id,w;
	vector<int>e;
}tr[N];
int n,m,s,tot=0,dfn[N],id[N];
void dfs1(int x,int fa,int dep){
	tr[x].fa=fa,tr[x].dep=dep,tr[x].size=1;
	int maxx=-1;
	for(auto it:tr[x].e){
		if(it==fa) continue;
		dfs1(it,x,dep+1);
		tr[x].size+=tr[it].size;
		if(tr[it].size>maxx) tr[x].maxson=it,maxx=tr[it].size;
	}
}
void dfs2(int x,int top){
	dfn[++tot]=tr[x].w,id[++tot]=x,tr[x].top=top,tr[x].id=tot;
	if(!tr[x].maxson) return;
	dfs2(tr[x].maxson,top);
	for(auto it:tr[x].e){
		if(it==tr[x].fa||it==tr[x].maxson) continue;
		dfs2(it,it);
	}
}
class XDS{
public:
	struct node{
		int maxx,sum,l,r;
	}tr[N*4];	
	inline void pushup(int x){
		tr[x].sum=tr[x*2].sum+tr[x*2+1].sum;
		tr[x].maxx=max(tr[x*2].maxx,tr[x*2+1].maxx);
	}
	void build(int x,int l,int r){
		tr[x].l=l,tr[x].r=r;
		if(l==r){
			tr[x].sum=tr[x].maxx=dfn[l];
			return;
		}
		int mid=(l+r)/2;
		build(x*2,l,mid),build(x*2+1,mid+1,r);
		pushup(x);
	}
	void change(int now,int x,int k){
		if(tr[now].l==tr[now].r){
			tr[now].maxx=tr[now].sum=k;
			return;
		}
		int mid=(tr[now].l+tr[now].r)/2;
		if(x<=mid) change(now*2,x,k);
		else change(now*2+1,x,k);
		pushup(now);
	}
	int query_sum(int x,int l,int r){
		if(tr[x].l>=l&&tr[x].r<=r) return tr[x].sum;
		int mid=(tr[x].l+tr[x].r)/2,sum=0;
		if(l<=mid) sum=query_sum(x*2,l,mid);
		if(r>mid) sum+=query_sum(x*2+1,mid+1,r);
		return sum;
	}
	int query_max(int x,int l,int r){
		if(tr[x].l>=l&&tr[x].r<=r) return tr[x].maxx;
		int mid=(tr[x].l+tr[x].r)/2,maxx=0;
		if(l<=mid) maxx=query_sum(x*2,l,mid);
		if(r>mid) maxx=max(maxx,query_sum(x*2+1,mid+1,r));
		return maxx;
	}
};

XDS xds;
inline void CHANGE(int u,int t){
	xds.change(1,tr[u].id,t);
}
inline int QSUM(int u,int v){
	int ans=0;
	while(tr[u].top!=tr[v].top){
		if(tr[u].dep<tr[v].dep) swap(u,v);
		int t=tr[u].top;
		ans+=xds.query_sum(1,tr[t].id,tr[u].id);
		u=tr[t].fa;
	}
	return ans;
}
inline int QMAX(int u,int v){
	int maxx=-0x3f3f3f3f;
	while(tr[u].top!=tr[v].top){
		if(tr[u].dep<tr[v].dep) swap(u,v);
		int t=tr[u].top;
		maxx=max(xds.query_sum(1,tr[t].id,tr[u].id),maxx);
		u=tr[t].fa;
	}	
	return maxx;
}

int main(){
	s=1;
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		tr[a].e.push_back(b),tr[b].e.push_back(a);
	}
	for(int i=1;i<=n;i++) cin>>tr[i].w;
	dfs1(s,s,1);
	dfs2(s,s);
	xds.build(1,1,n);
	scanf("%d",&m);
	while(m--){
		string op;
		int u,v;
		cin>>op>>u>>v;
		if(op=="CHANGE") CHANGE(u,v);
		if(op=="QSUM") cout<<QSUM(u,v)<<endl;
		if(op=="QMAX") cout<<QMAX(u,v)<<endl;
	}
}