Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int w[MAXN],c[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int top[MAXN],dep[MAXN],siz[MAXN],son[MAXN],fa[MAXN],rank[MAXN],th[MAXN],tot = 0; 

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rank[k] = ++tot;

	th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

struct node

{

	int lc,rc;

	int sum,max;

	node(){lc = rc = 0;}

}t[MAXN << 6];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void add(int &rt,int p,int k,int l,int r)

{

	if(rt == 0)rt = newnode();

	if(l == r)

	{

		t[rt].sum += k;t[rt].max += k;

		return;

	}

	if(p <= mid)add(t[rt].lc,p,k,l,mid);

	else add(t[rt].rc,p,k,mid + 1,r);

	t[rt].sum = t[rt].max = 0;

	if(t[rt].lc != 0)

	{

		t[rt].sum += t[t[rt].lc].sum;

		t[rt].max = max(t[rt].max,t[t[rt].lc].max);

	}

	if(t[rt].rc != 0)

	{

		t[rt].sum += t[t[rt].rc].sum;

		t[rt].max = max(t[rt].max,t[t[rt].rc].max);

	}

	return;

}

int sumw(int rt,int L,int R,int l,int r)

{

	if(rt == 0)return 0;

	if(L <= l && r <= R)return t[rt].sum;

	int res = 0;

	if(L <= mid)res += sumw(t[rt].lc,L,R,l,mid);

	if(R > mid)res += sumw(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int querysum(int x,int y)

{

	int cs = c[x];

	int res = 0;

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]])swap(x,y);

		res += sumw(root[cs],rank[top[x]],rank[x],1,n);

		x = fa[top[x]];

	}

	if(dep[x] < dep[y])swap(x,y);

	res += sumw(root[cs],rank[y],rank[x],1,n);

	return res;

}

int maxw(int rt,int L,int R,int l,int r)

{

	if(rt == 0)return 0;

	if(L <= l && r <= R)return t[rt].max;

	int res = 0;

	if(L <= mid)res = max(res,maxw(t[rt].lc,L,R,l,mid));

	if(R > mid)res = max(res,maxw(t[rt].rc,L,R,mid + 1,r));

	return res;

}

int querymax(int x,int y)

{

	int sc = c[x];

	int res = 0;

	while(top[x] != top[y])

	{

		if(dep[top[x]] < dep[top[y]])swap(x,y);

		res = max(res,maxw(root[sc],rank[top[x]],rank[x],1,n));

		x = fa[top[x]];

	}

	if(dep[x] < dep[y])swap(x,y);

	res = max(res,maxw(root[sc],rank[y],rank[x],1,n));

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d%d",&w[i],&c[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);

	dfs2(1,1);

	for(int i = 1;i <= 100000;++i)root[i] = newnode();

	string s;int x,y;

	for(int i = 1;i <= n;++i)add(root[c[i]],rank[i],w[i],1,n);

	for(int i = 1;i <= m;++i)

	{

		cin >> s >> x >> y;

		if(s == "CC")

		{

			add(root[c[x]],rank[x],-w[x],1,n);

			c[x] = y;

			add(root[c[x]],rank[x],w[x],1,n);

		}

		if(s == "CW")

		{

			add(root[c[x]],rank[x],-w[x],1,n);

			w[x] = y;

			add(root[c[x]],rank[x],w[x],1,n);

		}

		if(s == "QS")

		{

			printf("%d\n",querysum(x,y));

		}

		if(s == "QM")

		{

			printf("%d\n",querymax(x,y));

		}

	}

	

	return 0;

}