两个问题&进食后人

#include <iostream>
#include <vector>
using namespace std;
long long W[100100],C[100100],zhong[100100],root[100100],siz[100100],F[100100],rot[100100],n,deep[100100],id[100100],tot = 0,cnt = 0;
vector <long long> V[100100];
struct node{
	long long ls,rs,val,ma;
};
node T[2000100];
void dfs(long long x,long long f){
	long long i;
	siz[x]++;
	for(i = 0;i < V[x].size();i++){
		if(V[x][i] == f){
			continue;
		}
		dfs(V[x][i],x);
		siz[x] += siz[V[x][i]];
		if(siz[zhong[x]] < siz[V[x][i]]){
			zhong[x] = V[x][i];
		}
	}
}
void dfs2(long long x,long long f,long long r,long long d){
	long long i;
	tot++;
	id[x] = tot;
	deep[id[x]] = d;
	rot[id[x]] = id[r];
	F[id[x]] = id[f];
	if(zhong[x]){
		dfs2(zhong[x],x,r,d+1);
	}
	for(i = 0;i < V[x].size();i++){
		if(V[x][i] == f || V[x][i] == zhong[x]){
			continue;
		}
		dfs2(V[x][i],x,V[x][i],d+1);
	}
}
void add(long long &x,long long a,long long k,long long l,long long r){
	if(x == 0){
		cnt++;
		x = cnt;
	}
	if(l == r){
		T[x].val = k;
		T[x].ma = k;
		return;
	}
	long long mid = (l + r)>>1;
	if(a <= mid){
		add(T[x].ls,a,k,l,mid);
	}else{
		add(T[x].rs,a,k,mid+1,r);
	}
	T[x].val = T[T[x].ls].val + T[T[x].rs].val;
	T[x].ma = max(T[T[x].ls].ma,T[T[x].rs].ma);
	return;
}
long long Tquery(long long x,long long l,long long r,long long op,long long tl,long long tr){
	if(tl == l && tr == r){
		if(op == 1){
			return T[x].val;
		}else{
			return T[x].ma;
		}
	}
	long long mid = (tl + tr)>>1,a,ans;
	if(r <= mid){
		ans = Tquery(T[x].ls,l,r,op,tl,mid);
	}else if(l > mid){
		ans = Tquery(T[x].rs,l,r,op,mid+1,tr);
	}else{
		a = Tquery(T[x].ls,l,mid,op,tl,mid);
		ans = Tquery(T[x].rs,mid+1,r,op,mid+1,tr);
		if(op == 1){
			ans += a;
		}else{
			ans = max(a,ans);
		}
	}
	return ans;
}
long long query(long long x,long long y,long long c,long long op){
	long long a,ans = 0,ans2 = 0;
	while(rot[x] != rot[y]){
		if(deep[rot[x]] > deep[rot[y]]){
			a = Tquery(root[c],rot[x],x,op,1,n);
			ans += a;
			ans2 = max(ans2,a);
			x = F[rot[x]];
		}else{
			a = Tquery(root[c],rot[y],y,op,1,n);
			ans += a;
			ans2 = max(ans2,a);
			y = F[rot[y]];
		}
	}
	if(deep[x] > deep[y]){
		a = Tquery(root[c],y,x,op,1,n);
	}else{
		a = Tquery(root[c],x,y,op,1,n);
	}
	ans += a;
	ans2 = max(ans2,a);
	if(op == 1){
		return ans;
	}else{
		return ans2;
	}
}
char op[10];
int main(){
	long long q,i,x,y,c,ans;
	cin>>n>>q;
	for(i = 1;i <= n;i++){
		scanf("%lld%lld",&W[i],&C[i]);
	}
	for(i = 1;i < n;i++){
		scanf("%lld%lld",&x,&y);
		V[x].push_back(y);
		V[y].push_back(x);
	}
	dfs(1,0);
	dfs2(1,0,1,1);
	for(i = 1;i <= n;i++){
		add(root[C[i]],id[i],W[i],1,n);
	}
	for(i = 1;i <= q;i++){
		scanf("%s",op);
		if(op[1] == 'C'){
			scanf("%lld%lld",&x,&y);
			add(root[C[x]],id[x],0,1,n);
			C[x] = y;
			add(root[C[x]],id[x],W[x],1,n);
		}else if(op[1] == 'W'){
			scanf("%lld%lld",&x,&y);
			W[x] = y;
			add(root[C[x]],id[x],W[x],1,n);
		}else if(op[1] == 'S'){
			scanf("%lld%lld",&x,&y);
			ans = query(id[x],id[y],C[x],1);
			printf("%lld\n",ans);
		}else{
			scanf("%lld%lld",&x,&y);
			ans = query(id[x],id[y],C[x],2);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

node T[1000100];

void add(long long x,long long l,long long k){
	if(T[x].l == l && T[x].r == l){
		T[x].val = k;
		T[x].ma = k;
		return;
	}
	long long mid = (T[x].l + T[x].r)/2;
	if(l <= mid){
		if(T[x].ls == 0){
			cnt++;
			T[x].ls = cnt;
			T[T[x].ls].l = T[x].l;
			T[T[x].ls].r = mid;
		}
		add(T[x].ls,l,k);
	}else{
		if(T[x].rs == 0){
			cnt++;
			T[x].rs = cnt;
			T[T[x].rs].l = mid+1;
			T[T[x].rs].r = T[x].r;
		}
		add(T[x].rs,l,k);
	}
	T[x].val = T[T[x].ls].val + T[T[x].rs].val;
	T[x].ma = max(T[T[x].ls].ma,T[T[x].rs].ma);
	return;
}
long long Tquery(long long x,long long l,long long r,long long op){
	if(T[x].l == l && T[x].r == r){
		if(op == 1){
			return T[x].val;
		}else{
			return T[x].ma;
		}
	}
	long long mid = (T[x].l + T[x].r)/2,a,ans;
	if(r <= mid){
		ans = Tquery(T[x].ls,l,r,op);
	}else if(l > mid){
		ans = Tquery(T[x].rs,l,r,op);
	}else{
		a = Tquery(T[x].ls,l,mid,op);
		ans = Tquery(T[x].rs,mid+1,r,op);
		if(op == 1){
			ans += a;
		}else{
			ans = max(a,ans);
		}
	}
	return ans;
}