大概是一道树链剖分的裸题。可以看出如果不是查询相同宗教的这一点，就和普通的树链剖分毫无两样了。所以针对每一个宗教都单独开一棵线段树，变成单点修改+区间查询。只不过宗教数目很多，空间消耗太大所以只能开一棵总的再动态开点。
#include <bits/stdc++.h>
using namespace std;
#define maxn 200500
#define maxm 2000000
int n, q, cnp = , cnt, tot, root[maxn], name[maxn], head[maxn], w[maxn], c[maxn];
struct node
{
int id, size, fa, dep, hson, gra;
}P[maxn]; struct edge
{
int to, last;
}E[maxn]; struct tree
{
int sum, ext, lson, rson;
}T[maxm]; int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} void add(int x, int y)
{
E[cnp].to = y, E[cnp].last = head[x], head[x] = cnp ++;
} struct Segament_Tree
{
int query1(int p, int l, int r, int L, int R)
{
if(l <= L && r >= R) return T[p].sum;
if(l > R || r < L) return ;
int mid = (L + R) >> ;
return query1(T[p].lson, l, r, L, mid) + query1(T[p].rson, l, r, mid + , R);
} int query2(int p, int l, int r, int L, int R)
{
if(l <= L && r >= R) return T[p].ext;
if(l > R || r < L) return ;
int mid = (L + R) >> ;
return max(query2(T[p].lson, l, r, L, mid), query2(T[p].rson, l, r, mid + , R));
} void update(int &p, int L, int R, int x, int w)
{
if(!p) p = ++ cnt;
if(L == R)
{
T[p].sum = T[p].ext = w;
return;
}
int mid = (L + R) >> ;
if(x <= mid) update(T[p].lson, L, mid, x, w);
else update(T[p].rson, mid + , R, x, w);
T[p].sum = T[T[p].lson].sum + T[T[p].rson].sum;
T[p].ext = max(T[T[p].lson].ext, T[T[p].rson].ext);
} }ST[maxn]; struct Heavy_Light_Decomposition
{
int dfs(int u)
{
P[u].size = ;
for(int i = head[u]; i; i = E[i].last)
{
int v = E[i].to;
if(v == P[u].fa) continue;
P[v].dep = P[u].dep + , P[v].fa = u;
dfs(v);
P[u].size += P[v].size;
if(P[v].size > P[P[u].hson].size) P[u].hson = v;
}
} int dfs2(int u, int anc)
{
P[u].id = ++ tot, P[u].gra = anc, name[tot] = u;
if(P[u].hson) dfs2(P[u].hson, anc);
for(int i = head[u]; i; i = E[i].last)
{
int v = E[i].to;
if(v == P[u].hson || v == P[u].fa) continue;
dfs2(v, v);
}
} void update1(int x, int r)
{
ST[c[x]].update(root[c[x]], , tot, P[x].id, );
ST[r].update(root[r], , tot, P[x].id, w[x]);
c[x] = r;
} void update2(int x, int t)
{
ST[c[x]].update(root[c[x]], , tot, P[x].id, t);
w[x] = t;
} void query1(int x, int y)
{
int tx = P[x].gra, ty = P[y].gra;
int r = c[x];
int ans = ;
while(tx != ty)
{
if(P[tx].dep < P[ty].dep) swap(x, y), swap(tx, ty);
ans += ST[r].query1(root[r], P[tx].id, P[x].id, , tot);
x = P[tx].fa, tx = P[x].gra;
}
if(P[x].dep < P[y].dep) swap(x, y), swap(tx, ty);
ans += ST[r].query1(root[r], P[y].id, P[x].id, , tot);
printf("%d\n", ans);
} void query2(int x, int y)
{
int tx = P[x].gra, ty = P[y].gra;
int r = c[x];
int ans = ;
while(tx != ty)
{
if(P[tx].dep < P[ty].dep) swap(x, y), swap(tx, ty);
ans = max(ans, ST[r].query2(root[r], P[tx].id, P[x].id, , tot));
x = P[tx].fa, tx = P[x].gra;
}
if(P[x].dep < P[y].dep) swap(x, y), swap(tx, ty);
ans = max(ans, ST[r].query2(root[r], P[y].id, P[x].id, , tot));
printf("%d\n", ans);
} }HLD; int main()
{
n = read(), q = read();
for(int i = ; i <= n; i ++)
w[i] = read(), c[i] = read();
for(int i = ; i < n; i ++)
{
int x = read(), y = read();
add(x, y), add(y, x);
}
HLD.dfs(), HLD.dfs2(, );
for(int i = ; i < maxn; i ++) root[i] = ++ cnt;
for(int i = ; i <= n; i ++) ST[c[i]].update(root[c[i]], , tot, P[i].id, w[i]);
for(int i = ; i <= q; i ++)
{
string s;
cin >> s;
int x = read(), y = read();
if(s[] == 'C')
{
if(s[] == 'C') HLD.update1(x, y);
else HLD.update2(x, y);
}
else
{
if(s[] == 'S') HLD.query1(x, y);
else HLD.query2(x, y);
}
}
return ;
}