做法前面的大佬都说的很清楚了，这题的关键主要在于对宗教建线段树和动态开点。

既然是动态开点就要记录下每个节点的左右儿子，这里用引用调用来更新每个点的左右儿子。事实上能对答案产生贡献的只有有值的节点，所以对于没有值的节点我们不需要把它建出来，这样可以省不少空间。
这里仿照了Owen_codeisking大佬的写法。

void update(ll &p,ll l,ll r,ll pos,ll det)
{
    if(!p) p = ++tot;//新节点
    if(l == r)//到了要更新的点的位置。
    {
        tree[p].sum = det;
        tree[p].maxx = det;
        return;
    }
    ll mid = (l + r)>>1;
    if(pos <= mid)update(tree[p].ls,l,mid,pos,det);
    else update(tree[p].rs,mid + 1,r,pos,det);
    push_up(p,tree[p].ls,tree[p].rs);
    return;
}

（动态开点的tot不要和树剖更新编号的tot搞混）

值得注意的是，因为没有值的节点我们还没有建出来，所以在其他操作访问到这个节点的时候一定要加上这么一句以此来防止访问到奇怪的东西。

if(!p) p = ++tot;

还有一个注意的地方是这题先给出了城市的信息再建图，所以我们必须把信息存下来等建完图之后再更新（应该没人和我犯一样的错误吧）

其他部分就是树剖板子加上线段树板子了（别忘了城市在线段树上的编号是哦~）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=100010;
const ll INF=2147483647;
struct SegmentTree
{
    ll ls,rs,sum,maxx;
}tree[maxn * 40];//参考主席树开40倍。
struct node
{
    ll val,rel;
}c[maxn];
ll n,m,a[maxn],q,root[maxn],x,y,icur;
ll dep[maxn],fa[maxn],son[maxn],tot;
ll id[maxn],top[maxn],size[maxn];
string cur;
vector<ll> e[maxn];
bool vis[maxn];
//下面是树剖
void dfs1(ll x,ll step)
{
    vis[x] = 1;
    dep[x] = step;
    size[x] = 1;
    ll tem = -1;
    for(int i = 0;i < e[x].size();i++)
    {
        if(!vis[e[x][i]])
        {
            dfs1(e[x][i],step + 1);
            fa[e[x][i]] = x;
            size[x] += size[e[x][i]];
            if(size[e[x][i]] > tem)
            {
                tem = size[e[x][i]];
                son[x] = e[x][i];
            }
        }
    }
    return;
}
void dfs2(ll x,ll topf)
{
    vis[x] = 1;
    top[x] = topf;
    id[x] = ++icur;
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i = 0;i < e[x].size();i++)
    {
        if(!vis[e[x][i]])
        {
            dfs2(e[x][i],e[x][i]);
        }
    }
    return;
}
//下面是动态开点线段树（所以没有build函数）
void push_up(ll p,ll ls,ll rs)
{
    tree[p].sum = tree[ls].sum + tree[rs].sum;
    tree[p].maxx = max(tree[ls].maxx,tree[rs].maxx);
    return;
}
void insert(ll &p,ll pos,ll l,ll r,ll det)
{
    if(!p)p = ++tot;
    if(l == r)//这里并不需要=pos，因为访问叶节点的时候一定是pos
    {
        tree[p].sum = det;
        tree[p].maxx = det;
        return;
    }
    ll mid = (l + r)>>1;
    if(pos <= mid)insert(tree[p].ls,pos,l,mid,det);
    else insert(tree[p].rs,pos,mid + 1,r,det);
    push_up(p,tree[p].ls,tree[p].rs);
    return;
}
void del(ll p,ll l,ll r,ll pos)
{
    if(!p)return;
    if(l == r)
    {
        tree[p].sum = 0;
        tree[p].maxx = 0;
        return;
    }
    ll mid = (l + r)>>1;
    if(pos <= mid)del(tree[p].ls,l,mid,pos);
    else del(tree[p].rs,mid + 1,r,pos);
    push_up(p,tree[p].ls,tree[p].rs);
    return;
}
void update(ll &p,ll l,ll r,ll pos,ll det)
{
    if(!p) p = ++tot;//动态开点
    if(l == r)
    {
        tree[p].sum = det;
        tree[p].maxx = det;
        return;
    }
    ll mid = (l + r)>>1;
    if(pos <= mid)update(tree[p].ls,l,mid,pos,det);
    else update(tree[p].rs,mid + 1,r,pos,det);
    push_up(p,tree[p].ls,tree[p].rs);
    return;
}
ll qsum(ll p,ll l,ll r,ll il,ll ir)
{
    if(!p)return 0;如果是空节点。
    if(il <= l && ir >= r)return tree[p].sum;
    ll mid = (l + r)>>1;
    ll res = 0;
    if(il <= mid)res += qsum(tree[p].ls,l,mid,il,ir);
    if(ir > mid)res += qsum(tree[p].rs,mid + 1,r,il,ir); 
    return res;
}
ll qmax(ll p,ll l,ll r,ll il,ll ir)
{
    if(!p)return 0;
    if(il <= l && ir >= r)return tree[p].maxx;
    ll mid = (l + r)>>1;
    ll res = -1;
    if(il <= mid)res = max(res,qmax(tree[p].ls,l,mid,il,ir));
    if(ir > mid)res = max(res,qmax(tree[p].rs,mid + 1,r,il,ir));
    return res;
}
ll qtresum(ll p,ll x,ll y)
{
    ll res = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        res += qsum(p,1,n,id[top[x]],id[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    res += qsum(p,1,n,id[x],id[y]);
    return res;
}
ll qtremax(ll p,ll x,ll y)
{
    ll res = -1;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        res = max(res,qmax(p,1,n,id[top[x]],id[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    res = max(res,qmax(p,1,n,id[x],id[y]));
    return res;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        cin>>c[i].val>>c[i].rel;
    }
    for(int i = 1;i < n;i++)
    {
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    fa[1] = 1;
    dfs1(1,1);
    memset(vis,0,sizeof(vis));
    dfs2(1,1);
    for(int i = 1;i <= n;i++)
    {
        insert(root[c[i].rel],id[i],1,n,c[i].val);//这里是id[i]，不要弄错了。
    }
    while(m--)//其他操作都和普通树剖差不多。
    {
        cin>>cur>>x>>y;
        if(cur[0] == 'Q')
        {
            if(cur[1] == 'S')
            {
                cout<<qtresum(root[c[x].rel],x,y)<<"\n";
            }
            else
            {
                cout<<qtremax(root[c[x].rel],x,y)<<"\n";
            }
        }
        else
        {
            if(cur[1] == 'C')
            {
                del(root[c[x].rel],1,n,id[x]);
                c[x].rel = y;
                update(root[c[x].rel],1,n,id[x],c[x].val);
            }
            else
            {
                c[x].val = y;
                del(root[c[x].rel],1,n,id[x]);
                update(root[c[x].rel],1,n,id[x],c[x].val);
            }
        }
    }
    return 0;
}