1,2       N,Q<=10^3,C<=10^2     无 

 

      3,4       N,Q<=10^5,C<=10^2     链；无CC操作 

 

      5         N,Q<=10^5,C<=10^2     无CC，QM操作 

 

      6,7       N,Q<=10^5,C<=10^2     无CC 操作 

 

      8,9       N,Q<=10^5,C<=10^2     链

 

      10~12     N,Q<=10^5,C<=10       无

 

      13~16     N,Q<=10^5,C<=10^5     无QM操作

 

      17~20     N,Q<=10^5,C<=10^5     无

 

 

 

 

Solution：

部分分还是比较良心的

如果你在赛场上代码能力没有出现神奇的现象，那么块状树会有50分，树套树会有80分，单独处理链会有20分，离线树套树是满分，离(在)线lct也是满分。。。。还有很多得分的算法，不一一列举

 

这里介绍一种离线动态开结点的线段树(链剖)算法。。

因为是两个log而且常数极大。。需要玩好长时间的常数和内存才能过。。

 

假设所有点的颜色都是一样的，那么就是一个经典水题，直接链剖+线段树就能过了

如果颜色数是100范围内的，那么可以一个颜色开一棵树，对于一棵颜色为Col的树，我们把颜色不为Col的点的权值全部设为0，修改颜色的时候只需要把原来颜色的树上的该点权值设成0，修改现在的颜色的树上的该点的权值，这样我们就有50分了，玩一玩常数或者链的情况单独处理的话就有60分了。

现在颜色数是10^5范围内的，我们不可能开到这么多棵树。但是考虑点数只是在10^5范围内的，而且询问路径的两个端点的颜色，那么我们一棵树上的点可能没有必要包含全部的点。

有一个结论：如果把所有颜色可能为Col的点按照dfs序排列，那么可能在询问时要走过的点就是这些点以及所有两两相邻的点的lca，这样的话树Col上要用到的点显然是2*R的，R是可能颜色为Col的点数。

因为每次修改单点，所以Sigma(R)显然是O(N+Q)级别的。所以我们就开下了所有可能的点，只需要O(2*(N+Q))级别的内存。这样这个问题就解决了

 

丑陋的玩常数+内存的代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<tr1/unordered_map>
using namespace std;
using namespace tr1;
const int MAXN = 100010;
char buf[3600000], *buff = buf;
namespace Tree
{
	int tot, pos[MAXN], pop[MAXN], f[MAXN], d[MAXN][30], dep[MAXN];
	struct Eg { int v; Eg *ne; } e[MAXN * 2], *po[MAXN], *G = e;
	void add(int a, int b) { G->v = b; G->ne = po[a]; po[a] = G++; }
	void dfs(int x)
	{
		pos[x] = ++tot;
		dep[x] = dep[f[x]] + 1;
		int k = 0, y = f[x]; d[x][0] = y;
		while(d[y][k]) d[x][k+1] = d[y][k], y = d[y][k++];
		for(Eg *j = po[x]; j; j = j->ne)
			if(j->v != f[x]) f[j->v] = x, dfs(j->v);
		pop[x] = ++tot;
	}
	int Lca(int x, int y)
	{
		if(dep[x] < dep[y]) swap(x, y);
		int k = 0;
		while(k >= 0 && dep[x] >= dep[y])
			if(dep[d[x][k]] >= dep[y])
				x = d[x][k++]; else --k;
		if(x == y) return x;
		k = 0;
		while(d[x][0] != d[y][0])
			if(d[x][k] == d[y][k]) --k;
			else x = d[x][k], y = d[y][k++];
		return d[x][0];
	}
}
namespace CC
{
	int W[MAXN], q[MAXN];
	struct Tseg
	{
		int L, R, mx, sum; Tseg *lch, *rch;
		void Init(int l, int r)
		{
			L = l; R = r; lch = rch = 0x0;
			if(l == r) { sum = mx = W[l]; return; }
			int mid = (L + R) / 2; 
			(lch = new Tseg()) -> Init(L, mid);
			(rch = new Tseg()) -> Init(mid + 1, R);
			mx = max(lch->mx, rch->mx); sum = lch->sum + rch->sum;
		}
		int Querym(int l, int r)
		{
			if(L == l && R == r) return mx; int mid = (L + R) / 2;
			if(l > mid) return rch -> Querym(l, r); else
			if(r <=mid) return lch -> Querym(l, r); else
			return max(lch -> Querym(l, mid), rch -> Querym(mid + 1, r)); 
		}
		int Querys(int l, int r)
		{
			if(L == l && R == r) return sum; int mid = (L + R) / 2;
			if(l > mid) return rch -> Querys(l, r); else
			if(r <=mid) return lch -> Querys(l, r); else
			return lch -> Querys(l, mid) + rch -> Querys(mid + 1, r); 
		}
		void Modify(int pos, int y)
		{
			if(L == R) { sum = mx = y; return; } int mid = (L + R) / 2;
			if(pos > mid) rch -> Modify(pos, y); else lch -> Modify(pos, y);
			mx = max(lch->mx, rch->mx); sum = lch->sum + rch->sum;
		}
	};
	struct Ttree
	{
		unordered_map<int, Tseg*> seg;
		struct Eg { int v; Eg *ne; } **po, *G;
		unordered_map<int, int> Map, RMap, HMap;
		int N, root, *dep, *f, *head, *w, *size, *smap;
		void Newnode(int x) { RMap[Map[x] = ++N] = x; }
		void add(int a, int b) { a = Map[a]; b = Map[b]; G = new Eg(); G->v = b; G->ne = po[a]; po[a] = G++; }
		void Dfs1(int x)
		{
			dep[x] = dep[f[x]] + (size[x] = 1);
			for(Eg *j = po[x]; j; j = j->ne)
				f[j->v] = x, Dfs1(j->v), size[x] += size[j->v];
		}
		void Dfs2(int x)
		{
			int mx = 0, temp = 0;
			for(Eg *j = po[x]; j; j = j->ne)
				if(size[j->v] > mx) mx = size[temp = j->v];
			for(Eg *j = po[x]; j; j = j->ne)
				if(j->v == temp) head[j->v] = head[x]; else head[j->v] = j->v;
			for(Eg *j = po[x]; j; j = j->ne) Dfs2(j->v);
		}
		void InitNewTree()
		{
			dep = new int[N+10];	fill(dep, dep + N + 1, 0);
			head = new int[N+10];	fill(head, head + N + 1, 0);
			f = new int[N+10];		fill(f, f + N + 1, 0);
			w = new int[N+10];		fill(w, w + N + 1, 0); 
			size = new int[N+10];	fill(size, size + N + 1, 0);
			smap = new int[N+10];	fill(smap, smap + N + 1, 0);
			po = new Eg*[N+10];		for(int i = 0; i <= N; ++i) po[i] = NULL;
		}
		void Build(int x)
		{
			root = Map[x];			
			Dfs1(head[root] = root); Dfs2(root);
			for(int i = 1; i <= N; ++i)
			if(head[i] == i)
			{
				int h = 0, t = 1; q[1] = i;
				while(h < t)
				{
					int x = q[++h]; smap[x] = h;
					for(Eg *j = po[x]; j; j = j->ne)
						if(head[j->v] == i) q[++t] = j->v;
				}
				for(int j = 1; j <= t; ++j) W[smap[q[j]]] = w[q[j]];
				(seg[head[i]] = new Tseg()) -> Init(1, t);
			}
		}
		int Querysum(int a, int b)
		{
			int ret = 0, y = Tree::Lca(RMap[a], RMap[b]); y = Map[y];
			while(head[a] != head[y])
				ret += seg[head[a]] -> Querys(1, smap[a]), a = f[head[a]];
			while(head[b] != head[y])
				ret += seg[head[b]] -> Querys(1, smap[b]), b = f[head[b]];
			if(dep[a] > dep[b]) swap(a, b);
			return ret + seg[head[a]] -> Querys(smap[a], smap[b]);
		}
		int Querymax(int a, int b)
		{
			int ret = 0, y = Tree::Lca(RMap[a], RMap[b]); y = Map[y];
			while(head[a] != head[y])
				ret = max(ret, seg[head[a]] -> Querym(1, smap[a])), a = f[head[a]];
			while(head[b] != head[y])
				ret = max(ret, seg[head[b]] -> Querym(1, smap[b])), b = f[head[b]];
			if(dep[a] > dep[b]) swap(a, b);
			return max(ret, seg[head[a]] -> Querym(smap[a], smap[b]));
		}
	} *T[MAXN];
	int Querysum(int c, int a, int b) { a = (T[c] -> Map[a]); b = (T[c] -> Map[b]); return T[c] -> Querysum(a, b); }
	int Querymax(int c, int a, int b) { a = (T[c] -> Map[a]); b = (T[c] -> Map[b]); return T[c] -> Querymax(a, b); }
	void Changec(int x, int a, int b, int w)
	{
		int u = (T[a] -> Map[x]); T[a] -> seg[T[a]->head[u]] -> Modify( T[a]->smap[u], 0 );
			u = (T[b] -> Map[x]); T[b] -> seg[T[b]->head[u]] -> Modify( T[b]->smap[u], w );
	}
	void Changew(int x, int a, int b, int c) { int u = (T[c] -> Map[x]); T[c] -> seg[T[c]->head[u]] -> Modify( T[c]->smap[u], b ); }
}
namespace FAK
{
	int N, M, T;
	int can[MAXN], vis[MAXN];
	int sta[MAXN], f[MAXN], sta2[MAXN];
	struct Tque { int a, b; char ord; } Q[MAXN];
	struct Tnode { int w, c, id; Tnode() {} Tnode(int _w, int _c, int _id) { w = _w; c = _c; id = _id; } } t[MAXN * 2];
	bool cmpc(Tnode a, Tnode b) { return a.c < b.c; }
	bool cmpw2(Tnode a, Tnode b) { return a.w > b.w; }
	bool cmpid(Tnode a, Tnode b) { return a.id < b.id; }
	bool cmpTreedfs(int a, int b) { return Tree::pos[a] < Tree::pos[b]; }
	inline int read(int &x)
	{
		
		x = 0;
		while (*buff > '9' || *buff < '0') ++buff;
		while (*buff >='0' && *buff <='9') x = x * 10 + *buff ++ -48;
		return x;
	}
	inline void read(char x[])
	{
		x[0] = x[1] = x[2] = 0x0; int len = 0;
		while (*buff != 'C' && *buff != 'Q') ++buff;
		while (*buff =='C' || *buff == 'Q' || *buff == 'M' || *buff == 'W' || *buff == 'S') x[len++] = *buff++;
	}
	void Init()
	{
		fread(buf, 1, 3600000, stdin);
		read(N); read(M); T = N;
		for(int i = 1; i <= N; ++i)
			read(t[i].w), read(t[i].c), t[i].id = i;
		for(int i = 1, a, b; i < N; ++i)
			read(a), read(b), Tree::add(a, b), Tree::add(b, a);
		for(int i = 1; i <= M; ++i)
		{
			char ord[3]; read(ord); read(Q[i].a); read(Q[i].b);
			if((Q[i].ord = ord[1]) == 'C') t[++T] = Tnode(0, Q[i].b, Q[i].a);
		}
		Tree::dfs(1);
		sort(t + 1, t + T + 1, cmpc);
		for(int l = 1, r = 1; l <= T; l = r + 1)
		{
			int cnt = 0, cnt1;
			while(t[l].c == t[r + 1].c) ++r;
			CC::T[t[l].c] = new CC::Ttree();
			for(int i = l; i <= r; ++i)
			if(CC::T[t[l].c] -> Map.find(t[i].id) == CC::T[t[l].c] -> Map.end())
				CC::T[t[l].c] -> Newnode(t[i].id), f[sta[cnt++] = t[i].id] = 0;
			sort(sta, sta + cnt, cmpTreedfs); cnt1 = cnt;
			for(int i = 0; i < cnt; ++i)
			{
				int x = sta[i], y = sta[i+1]; if(i == cnt-1) y = sta[0]; int z = Tree::Lca(x, y);
				if(CC::T[t[l].c] -> Map.find(z) == CC::T[t[l].c] -> Map.end()) CC::T[t[l].c] -> Newnode(z), f[sta[cnt1++] = z] = 0;
			}
			sort(sta, sta + cnt1, cmpTreedfs);
			sta2[0] = 0;
			for(int i = 0, top = 0; i < cnt1; ++i)
			{
				while(top > 0 && Tree::pos[sta[i]] > Tree::pop[sta2[top]]) --top;
				f[sta[i]] = sta2[top]; sta2[++top] = sta[i];
			}
			CC::T[t[l].c] -> InitNewTree();
			for(int i = 1; i < cnt1; ++i) CC::T[t[l].c] -> add(f[sta[i]], sta[i]);
			CC::T[t[l].c] -> Build(sta[0]);
		}
	}
	void Query()
	{
		sort(t + 1, t + T + 1, cmpw2); sort(t + 1, t + N + 1, cmpid);
		for(int i = 1; i <= N; ++i) CC::Changew(i, 0, t[i].w, t[i].c);
		for(int i = 1, a, b; i <= M; ++i)
		{
			char ord = Q[i].ord; a = Q[i].a; b = Q[i].b;
			if(ord == 'S') printf("%d\n", CC::Querysum(t[a].c, a, b));
			if(ord == 'M') printf("%d\n", CC::Querymax(t[a].c, a, b));
			if(ord == 'C') CC::Changec(a, t[a].c, b, t[a].w), t[a].c = b;
			if(ord == 'W') CC::Changew(a, t[a].w, b, t[a].c), t[a].w = b;
		}		
	}
	void Solve()
	{
		Init();
		Query();
	}
}
int main()
{
	freopen("travel.in", "r", stdin);
	freopen("travel.out", "w", stdout);
	
	FAK::Solve();
	
	return 0;
}