🧩 问题核心与约束分析

题目要求我们在一个树形结构的城市网络上支持以下操作：

• 宗教修改（CC x c）：更改城市 $x$ 的宗教。
• 评级修改（CW x w）：更改城市 $x$ 的评级。
• 路径查询（QS x y 和 QM x y）：查询树上路径上相同宗教城市的评级总和或最大值。

关键点：

• 查询时只考虑与起点和终点宗教相同的城市。
• 城市数 $N$ 和操作数 $Q$ 最多为 $10^5$，宗教种类 $C$ 最多为 $10^5$。
• 需要高效的树上路径查询和点更新。

💡 核心思路：树链剖分 + 动态开点线段树

此问题的标准解法是结合 树链剖分（Heavy-Light Decomposition, HLD） 和 动态开点线段树（Dynamic Opening Segment Tree）。

🔹 第一步：树链剖分

树链剖分将树划分为若干条链，将树上的路径查询转化为若干段连续区间的查询。

1. 第一次DFS：计算每个节点的父节点、深度、子树大小、重儿子。
2. 第二次DFS：分配节点在DFS序中的位置（优先处理重儿子，保证重链上节点编号连续），记录链顶。

🔹 第二步：为每种宗教建立动态开点线段树

由于宗教种类 $C$ 可能很大（最多 $10^5$），且每个城市信仰一种宗教，我们不能直接为每种宗教建立一棵完整的线段树（内存无法承受）。

动态开点线段树可以解决这个问题：

• 初始时，所有线段树均为空。
• 当需要修改或查询时，按需创建节点。
• 每个节点记录：区间和、区间最大值（根据查询需求）。

🔹 第三步：操作实现

1. 初始化：

   • 根据初始宗教和评级，在对应宗教的线段树中，于该城市DFS序的位置插入其评级。

2. 宗教修改（CC x c）：

   • 在原宗教的线段树中，将城市 $x$ 对应的位置删除（评级置0或移除节点）。
   • 在新宗教 $c$ 的线段树中，在城市 $x$ 对应的位置插入其当前评级。

3. 评级修改（CW x w）：

   • 在城市 $x$ 当前宗教对应的线段树中，更新其DFS序位置上的评级值。

4. 路径查询（QS x y / QM x y）：

   • 确定查询的宗教 $c$（起点 $x$ 的宗教）。
   • 在宗教 $c$ 的线段树中，查询路径 $x$ 到 $y$ 上所有城市的评级总和或最大值。
   • 利用树链剖分，将路径拆分成若干条重链上的连续区间，分别在线段树中查询后再合并结果。

🧮 算法实现与细节

代码框架（仅供参考）

以下是基于常见实现方式整理的主要逻辑框架：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;

// 树链剖分相关
vector<int> G[MAXN];
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnk[MAXN], cnt;

// 第一次DFS：计算父节点、深度、子树大小、重儿子
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    son[u] = -1;
    for (int v : G[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (son[u] == -1 || siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

// 第二次DFS：分配DFS序，构建重链
void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    if (son[u] == -1) return;
    dfs2(son[u], tp); // 优先处理重儿子
    for (int v : G[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v); // 轻儿子开启新链
    }
}

// 动态开点线段树节点
struct Node {
    int lc, rc; // 左右儿子编号
    int sum, max_val;
} tree[MAXN * 40]; // 根据内存情况调整倍数
int root[MAXN], tot; // root[c]：宗教c的线段树根节点

// 更新节点信息
void pushup(int p) {
    tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
    tree[p].max_val = max(tree[tree[p].lc].max_val, tree[tree[p].rc].max_val);
}

// 动态开点更新：在线段树中修改位置pos的值为val
void update(int &p, int l, int r, int pos, int val) {
    if (!p) p = ++tot; // 动态开点
    if (l == r) {
        tree[p].sum = tree[p].max_val = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(tree[p].lc, l, mid, pos, val);
    else update(tree[p].rc, mid + 1, r, pos, val);
    pushup(p);
}

// 线段树区间查询：查询[ql, qr]的和或最大值
int query_sum(int p, int l, int r, int ql, int qr) {
    if (!p || ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[p].sum;
    int mid = (l + r) >> 1;
    return query_sum(tree[p].lc, l, mid, ql, qr) + 
           query_sum(tree[p].rc, mid + 1, r, ql, qr);
}

int query_max(int p, int l, int r, int ql, int qr) {
    if (!p || ql > r || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[p].max_val;
    int mid = (l + r) >> 1;
    return max(query_max(tree[p].lc, l, mid, ql, qr),
               query_max(tree[p].rc, mid + 1, r, ql, qr));
}

// 树链剖分路径查询：在宗教c的线段树上查询路径x-y的和或最大值
int path_query(int x, int y, int c, bool is_max) {
    int res = is_max ? 0 : 0; // 初始值：和初始为0，最大值初始为0或根据题目调整
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        int l = dfn[top[x]], r = dfn[x];
        if (is_max) {
            res = max(res, query_max(root[c], 1, cnt, l, r));
        } else {
            res += query_sum(root[c], 1, cnt, l, r);
        }
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    int l = dfn[x], r = dfn[y];
    if (is_max) {
        res = max(res, query_max(root[c], 1, cnt, l, r));
    } else {
        res += query_sum(root[c], 1, cnt, l, r);
    }
    return res;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<int> W(n+1), C(n+1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &W[i], &C[i]);
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // 树链剖分
    cnt = 0;
    dfs1(1, 0);
    dfs2(1, 1);
    
    // 初始化线段树：根据初始宗教和评级插入
    for (int i = 1; i <= n; i++) {
        update(root[C[i]], 1, cnt, dfn[i], W[i]);
    }
    
    while (q--) {
        char op[5];
        int x, y;
        scanf("%s%d%d", op, &x, &y);
        if (op[0] == 'C' && op[1] == 'C') {
            // 宗教修改：从原宗教删除，加入新宗教
            update(root[C[x]], 1, cnt, dfn[x], 0); // 原宗教中删除
            C[x] = y;
            update(root[C[x]], 1, cnt, dfn[x], W[x]); // 新宗教中插入
        } else if (op[0] == 'C' && op[1] == 'W') {
            // 评级修改
            W[x] = y;
            update(root[C[x]], 1, cnt, dfn[x], W[x]);
        } else if (op[0] == 'Q' && op[1] == 'S') {
            // 查询路径和
            printf("%d\n", path_query(x, y, C[x], false));
        } else if (op[0] == 'Q' && op[1] == 'M') {
            // 查询路径最大值
            printf("%d\n", path_query(x, y, C[x], true));
        }
    }
    return 0;
}

⚠️ 注意事项

1. 内存管理：动态开点线段树的内存池大小需要仔细设置，通常为 $O(N \log N)$ 级别。
2. 初始值处理：注意评级为0的情况，以及查询最大值时对空区间的处理。
3. 树链剖分细节：注意DFS序的分配、重链的划分，以及路径查询时链的跳跃。
4. 宗教相同保证：题目保证查询时起点和终点宗教相同，因此可以直接使用起点的宗教进行查询。
5. 效率分析：
   • 树链剖分路径查询：$O(\log^2 N)$
   • 线段树操作：$O(\log N)$
   • 总体复杂度：$O(Q \log^2 N)$，可以通过 $N, Q \leq 10^5$ 的数据。

💎 总结

这道题的核心在于：

1. 树链剖分：将树上路径查询转化为区间查询。
2. 动态开点线段树：按宗教管理信息，避免内存爆炸。
3. 操作处理：妥善处理宗教变更和评级更新带来的线段树变动。