「POI 2020/2021 R1」Gang Biciaków 题解

算法概述

本题解使用带修莫队算法（Mo's algorithm with updates）解决动态树路径颜色计数问题。该算法将树结构转化为欧拉序，然后通过莫队算法处理路径查询和颜色修改。

核心思想

1. 树转序列（欧拉序）

void pre_dfs(int u, int p) {
    tin[u] = timer++;      // 进入时间戳
    
    for (auto [v, c, idx] : G[u]) {
        if (v == p) continue;
        a[v] = c;
        who[idx] = v;      // 记录边对应的节点
        pre_dfs(v, u);
    }
    
    tout[u] = timer++;     // 离开时间戳
}

• 欧拉序性质：节点 $u$ 的子树在区间 $[tin[u], tout[u]]$ 中
• 路径表示：从根到节点 $u$ 的路径对应欧拉序前缀 $[1, tin[u]]$

2. 带修莫队框架

struct Query {
    int l, r, idx;  // l: tin[u], r: 最后一个修改的时间戳
    bool operator < (const Query other) const {
        int block_a = l / B, block_b = other.l / B;
        if (block_a != block_b) return block_a < block_b;
        return ((block_a & 1) ? (r > other.r) : (r < other.r));
    }
};

三维莫队：

• 维度1：欧拉序位置（查询区间）
• 维度2：修改时间（处理颜色更新）
• 分块大小 $B = \sqrt{n}$ 保证复杂度

关键数据结构

1. 颜色计数

int cnt;           // 当前不同颜色数量
int freq[N];       // 每种颜色的出现次数

2. 修改记录

pair<int, int> in[N];   // 修改操作：{节点, 新颜色}
pair<int, int> out[N];  // 回滚操作：{节点, 旧颜色}

3. 欧拉序列

int E[N];          // 欧拉序列，正数表示进入，负数表示离开

算法流程

1. 预处理阶段

// 建立欧拉序
pre_dfs(1, 1);

// 构建欧拉序列
for (int i = 1; i <= n; i++) {
    E[tin[i]] = i;     // 进入节点
    E[tout[i]] = -i;   // 离开节点（负号标记）
}

2. 查询处理

vector<int> mo_algorithm(vector<Query> Q) {
    // 对查询排序（莫队顺序）
    sort(Q.begin(), Q.end());
    
    int cur_l = 0, cur_r = -1;
    for (Query q : Q) {
        // 调整左边界（欧拉序）
        while (cur_l > q.l) {
            int u = E[cur_l];
            (u < 0) ? add(-u) : remove(u);
            cur_l--;
        }
        
        // 调整右边界（修改时间）
        while (cur_r < q.r) {
            cur_r++;
            auto [u, c] = in[cur_r];
            update(u, c, tin[u] <= cur_l && tout[u] > cur_l);
        }
        
        // 对称调整...
        
        ans[q.idx] = cnt;  // 记录答案
    }
    return ans;
}

关键操作实现

1. 节点添加/删除

void add(int u) {
    if (freq[a[u]] == 0) cnt++;
    freq[a[u]] += 1;
}

void remove(int u) {
    if (freq[a[u]] == 1) cnt--;
    freq[a[u]] -= 1;
}

2. 颜色更新

void update(int u, int c, bool alive) {
    if (alive) {
        // 如果节点在当前区间内，需要更新计数
        if (freq[a[u]] == 1) cnt--;
        freq[a[u]] -= 1;
        
        if (freq[c] == 0) cnt++;
        freq[c] += 1;
    }
    a[u] = c;  // 更新节点颜色
}

复杂度分析

• 时间复杂度：$O(n^{5/3})$（三维莫队的标准复杂度）
  • 欧拉序构建：$O(n)$
  • 莫队算法：$O(n^{5/3})$
• 空间复杂度：$O(n + m + q)$

算法优势

1. 支持动态修改：能够处理颜色更新操作
2. 离线处理：批量处理所有查询，提高效率
3. 通用性强：适用于各种树结构和颜色分布

适用场景

这种方法特别适用于：

• 需要支持颜色修改的场景
• 查询次数较多的场景
• 对在线性要求不高的应用

完整算法流程

1. 输入：树结构、初始颜色、查询和修改序列
2. 预处理：DFS建立欧拉序，记录时间戳
3. 构建：创建欧拉序列和修改记录数组
4. 处理：使用带修莫队处理所有查询
5. 输出：按原顺序输出查询结果