1. 什么是树上莫队

树上莫队（Mo's Algorithm on Tree）是经典莫队算法在树形结构上的扩展，用于高效处理树上的离线路径查询问题。它将树上的路径查询转化为欧拉序上的区间查询，从而利用莫队算法的分块思想，在近似 O(n√n) 的时间复杂度内回答大量查询。

2. 核心思想与转化

2.1 欧拉序与路径表示

树上莫队的关键在于将树形结构“拍平”成线性序列。我们使用树的欧拉序（Euler Tour Order）：

• 第一次访问节点时记录（进入时间 in[u]）
• 离开节点时再次记录（离开时间 out[u]）

这样每个节点在欧拉序中出现两次，路径查询可以转化为欧拉序上的区间查询。

2.2 路径到区间的转化

对于树上两点 u 和 v 的路径查询（假设 LCA 为 u 和 v 的最近公共祖先）：

1. 如果 u 是 v 的祖先：查询区间为 [in[u], in[v]]
2. 如果 v 是 u 的祖先：查询区间为 [in[v], in[u]]
3. 一般情况（u 和 v 没有祖先关系）：查询区间为 [out[u], in[v]] ∪ {LCA}

3. 算法框架与实现

3.1 预处理步骤

const int MAXN = 1e5 + 5;
vector<int> g[MAXN];
int in[MAXN], out[MAXN], euler[MAXN * 2], timestamp;
int depth[MAXN], fa[MAXN][20]; // 用于求LCA

void dfs(int u, int p) {
    in[u] = ++timestamp;
    euler[timestamp] = u;
    depth[u] = depth[p] + 1;
    fa[u][0] = p;
    
    for (int i = 1; i < 20; i++) 
        fa[u][i] = fa[fa[u][i-1]][i-1];
    
    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
    
    out[u] = ++timestamp;
    euler[timestamp] = u;
}

3.2 莫队结构体定义

struct Query {
    int l, r, id, lca;
    // 按莫队排序规则
    bool operator<(const Query &other) const {
        if (l / block_size != other.l / block_size)
            return l / block_size < other.l / block_size;
        return (l / block_size & 1) ? r > other.r : r < other.r;
    }
};

vector<Query> queries;
int block_size = sqrt(2 * n); // 欧拉序长度为2n

3.3 核心维护函数

int cnt[MAXN], ans, res[MAXN];
bool vis[MAXN]; // 记录节点在当前区间出现次数奇偶性

void add(int pos) {
    int node = euler[pos];
    vis[node] ^= 1; // 切换奇偶性
    if (vis[node]) {
        // 节点第一次出现
        cnt[color[node]]++;
        if (cnt[color[node]] == 1) ans++;
    } else {
        // 节点第二次出现
        cnt[color[node]]--;
        if (cnt[color[node]] == 0) ans--;
    }
}

void del(int pos) {
    add(pos); // 树上莫队中add和del操作对称
}

4. 典型应用场景

4.1 路径颜色计数

查询树上两点间路径上不同颜色的数量，这是树上莫队最经典的应用。

4.2 路径权值统计

统计路径上满足某种条件的节点权值，如最大值、最小值、异或和等。

4.3 子树查询转化

通过欧拉序将子树查询转化为区间查询，但通常有更高效的DFS序解法。

5. 时间复杂度分析

• 预处理：DFS求欧拉序和LCA，O(n log n)
• 排序：O(q log q)，q为查询数量
• 莫队处理：O((n+q)√n)，其中n为欧拉序长度（2n）
• 总复杂度：O(n log n + (n+q)√n)

6. 优化技巧

6.1 奇偶化排序

在莫队排序中加入奇偶化优化，减少指针移动距离：

bool operator<(const Query &other) const {
    if (l / block_size != other.l / block_size)
        return l / block_size < other.l / block_size;
    return (l / block_size & 1) ? r > other.r : r < other.r;
}

6.2 块大小调整

根据具体问题调整块大小，经验公式：block_size = n / sqrt(q)

6.3 预处理LCA

使用倍增、树剖或Tarjan离线算法预处理LCA，避免每次查询都计算。

7. 实战例题与代码

7.1 SPOJ COT2 - Count on a tree II

经典树上莫队模板题，统计路径上不同颜色的数量。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 40005, MAXQ = 100005;
// ... 完整实现代码（略）
int main() {
    // 读入树和颜色
    // 预处理欧拉序和LCA
    // 处理查询并输出答案
    return 0;
}

7.2 自定义问题：路径异或和

查询树上两点间路径上所有节点权值的异或和：

void add(int pos) {
    int node = euler[pos];
    vis[node] ^= 1;
    if (vis[node]) {
        xor_sum ^= val[node];
    } else {
        xor_sum ^= val[node];
    }
}

8. 与树分块的比较

特性	树上莫队	树分块
时间复杂度	O((n+q)√n)	O(n√n)
空间复杂度	O(n)	O(n√n)
适用场景	离线路径查询	在线/离线均可
代码复杂度	中等	较高
修改操作	困难（需带修莫队）	相对容易

9. 常见陷阱与注意事项

1. LCA处理：一般情况需要单独考虑LCA节点，因为它在区间中只出现一次
2. 数组大小：欧拉序数组要开2倍节点数
3. vis数组：记录节点出现奇偶性，而不是简单计数
4. 块大小：根据实际问题调整，不同问题最优块大小可能不同
5. 排序优化：务必使用奇偶化排序减少常数

10. 总结

树上莫队是处理树上离线路径查询的强大工具，通过欧拉序将树形问题转化为序列问题，再利用莫队的分块思想达到近似O(n√n)的效率。虽然有一定学习曲线，但掌握后能解决许多树上统计问题。在实际应用中，需要根据具体问题灵活调整维护函数和优化参数。

学习建议：从SPOJ COT2开始实践，理解欧拉序转化和奇偶性维护的本质，再尝试解决更复杂的问题。