题目理解

我们有一个树形结构的城市网络，每个城市售卖不同价值的珠宝。从城市 $u$ 到 $v$ 的行程中（$v$ 在 $u$ 到首都的路径上），初始手上有价值 $c$ 的珠宝，每经过一个城市，如果该城市珠宝价值严格大于当前手中所有珠宝，就会购买。

目标是计算每次行程的购买次数。

问题分析

1. 路径性质

• 由于 $v$ 在 $u$ 到首都的路径上，路径是唯一的
• 路径方向：从 $u$ 到 $v$ 是向首都方向移动

2. 购买条件

购买发生在当前城市珠宝价值严格大于手中所有珠宝价值时，购买后手中珠宝价值更新为该城市珠宝价值。

算法思路

1. 预处理 - 倍增数组

使用三种倍增数组来优化查询：

父节点数组

int fa[100005][20];  // fa[u][i] 表示u的2^i级祖先

路径最大值数组

int maxx[100005][20]; // maxx[u][i] 表示u到其2^i级祖先路径上的最大值

下一次购买位置数组

int nxt[100005][20]; // nxt[u][i] 表示从u出发的下一次购买的2^i级跳转
int cha[100005];     // cha[u] 表示从u到根节点的购买次数

2. DFS预处理

void dfs(int root, int father) {
    fa[root][0] = father;
    maxx[root][0] = val[root];
    dep[root] = dep[father] + 1;
    
    // 构建倍增数组
    for (int i = 1; i <= 19; i++) {
        fa[root][i] = fa[fa[root][i - 1]][i - 1];
        maxx[root][i] = max(maxx[root][i - 1], maxx[fa[root][i - 1]][i - 1]);
    }
    
    // 计算下一次购买位置
    int op = root;
    int _ = val[root];
    for (int i = 19; i >= 0; i--) {
        if (max(_, maxx[fa[op][0]][i]) <= val[root]) {
            _ = max(_, maxx[fa[op][0]][i]);
            op = fa[op][i];
        }
    }
    op = fa[op][0];
    nxt[root][0] = op;
    
    if (op != 0)
        cha[root] = cha[op] + 1;
        
    // 构建nxt的倍增数组
    for (int i = 1; i <= 19; i++) {
        nxt[root][i] = nxt[nxt[root][i - 1]][i - 1];
    }
}

3. 查询处理

void solve(int u, int v, int c) {
    int ans = 0;
    
    // 检查起点u是否需要购买
    if (c < val[u]) {
        ans++;
        c = val[u];
    }
    
    // 找到从u出发第一个需要购买的位置
    int op = u;
    int _ = c;
    for (int i = 19; i >= 0; i--) {
        if (max(_, maxx[fa[op][0]][i]) <= c) {
            _ = max(_, maxx[fa[op][0]][i]);
            op = fa[op][i];
        }
    }
    op = fa[op][0];
    
    // 如果第一个购买点在v之前，计数并继续
    if (op != 0 && dep[op] >= dep[v]) {
        ans++;
    }
    
    // 如果已经到达v，直接返回
    if (dep[op] <= dep[v]) {
        cout << ans << "\n";
        return;
    }
    
    // 使用nxt数组快速跳转到v
    int kl = 0;
    for (int i = 19; i >= 0; i--) {
        if (dep[nxt[op][i]] >= dep[v]) {
            op = nxt[op][i];
            kl += (1 << i);
        }
    }
    
    ans += kl;
    cout << ans << "\n";
}

关键算法细节

1. 寻找第一个购买点

从当前节点向上跳转，找到第一个珠宝价值大于当前手中最大价值的城市：

• 使用倍增法在O(logN)时间内找到
• 比较路径上的最大值与当前手中价值

2. 快速跳转计数

一旦找到第一个购买点，使用预处理的nxt数组快速计算到目标点的购买次数：

• nxt[u][0] 表示从u出发的下一个购买位置
• 通过倍增快速计算路径上的购买次数

3. 深度比较

使用深度来判断是否到达目标点v，确保在正确的位置停止。

复杂度分析

• 预处理：O(N log N) - DFS构建倍增数组
• 每次查询：O(log N) - 倍增跳转
• 总复杂度：O((N + Q) log N)
• 空间复杂度：O(N log N)

算法优化

1. 倍增思想

• 将线性查询优化为对数级
• 预处理各种跳转信息

2. 路径最大值维护

• 在倍增数组中同时维护路径最大值
• 支持快速判断是否需要购买

3. 购买链预处理

• 预处理每个节点的下一次购买位置
• 形成购买链，支持快速跳转计数

算法标签

• 树结构：树上的路径查询
• 倍增法：使用二进制提升优化查询
• 预处理：预先计算各种跳转信息
• 贪心思想：购买决策的局部最优性

总结

这道题通过巧妙的倍增预处理，解决了树上路径的购买计数问题：

1. 问题转化：将购买计数转化为路径跳转问题
2. 倍增预处理：构建父节点、最大值、下一次购买三个倍增数组
3. 高效查询：利用预处理信息在O(logN)时间内回答查询
4. 边界处理：正确处理起点购买和路径终点的各种情况

该解法充分利用了树结构的特性和倍增法的优势，实现了大规模数据下的高效查询。