---

题目分析

这个棋盘是无限完全二叉树 + 每层水平链表。

关键：我们需要将路径字符串转换成节点在树中的坐标，然后计算两个坐标之间的最短路径。

---

坐标表示法

我们可以用 (层数, 该层索引) 表示节点位置：

• 根节点：(0, 0)
• 左子节点：层数+1，索引变为 父索引*2
• 右子节点：层数+1，索引变为 父索引*2 + 1
• 父节点：层数-1，索引变为 父索引 = 子索引/2（整除）
• 左移 L：层数不变，索引-1
• 右移 R：层数不变，索引+1

---

路径解析

给定路径（如 221LU），从根 (0,0) 开始，按字符更新坐标。

注意：U 会回到父节点，可能改变层数和索引。

---

最短路径计算

假设：

• 节点 A 坐标：(levelA, indexA)
• 节点 B 坐标：(levelB, indexB)

步骤：

1. 先统一层数：让较深的节点向上走 |levelA - levelB| 步到同一层
2. 再水平移动：在同一层，从左索引到右索引需要 |indexA - indexB| 步（因为同一层是链表）
3. 但是水平移动可能不是最优？因为可以上下绕路？

实际上，由于同一层是链表，水平移动就是直接走。但如果层数不同，需要先对齐层数，然后水平移动。

但可能绕到公共祖先再下来更短？我们需要考虑：

---

更优策略

设 lca_level 是 A 和 B 的最低公共祖先所在层数。

• 从 A 向上走到 lca_level，步数 = levelA - lca_level
• 从 B 向上走到 lca_level，步数 = levelB - lca_level
• 在 lca_level 层，从 A 的祖先水平移动到 B 的祖先，步数 = |indexA >> (levelA - lca_level) - indexB >> (levelB - lca_level)|

总步数 = 上行步数 + 水平步数 + 下行步数？不对，这里我们只上到公共祖先，然后水平移动，不需要再下行（因为题目是 A→B 最短路径，不是回到根）。

实际上，A→B 的最短路径是：

1. A 向上走到某个共同层 k（k ≤ min(levelA, levelB)）
2. 在该层水平移动
3. 再向下走到 B

但水平移动只能在同一层进行，所以必须走到同一层才能水平移动。

---

关键公式

设我们选择在层 k 进行水平移动，其中 0 ≤ k ≤ min(levelA, levelB)。

• A→k 层：levelA - k 步（向上）
• 在 k 层，A 的祖先索引 = indexA >> (levelA - k)
• 在 k 层，B 的祖先索引 = indexB >> (levelB - k)
• 水平移动步数 = |indexA >> (levelA - k) - indexB >> (levelB - k)|
• k 层→B：levelB - k 步（向下）

总步数： [ \text{dist}(k) = (levelA - k) + |indexA >> (levelA - k) - indexB >> (levelB - k)| + (levelB - k) ] [ = levelA + levelB - 2k + |indexA >> (levelA - k) - indexB >> (levelB - k)| ]

我们需要对 k = 0..min(levelA, levelB) 求最小值。

---

算法步骤

1. 解析两条路径，得到 (levelA, indexA) 和 (levelB, indexB)
2. 计算 min_level = min(levelA, levelB)
3. 对 k 从 0 到 min_level，计算 dist(k)，取最小值
4. 输出最小 dist

复杂度：O(min(levelA, levelB))，但 level 最大可能是字符串长度 1e5，直接枚举会超时。

---

优化

观察：

• 当 k 减小（往上层走），水平距离可能增大，但 -2k 会减小
• 我们只需在水平距离发生变化的 k 处检查，因为水平距离是右移差值，变化点不多

实际上，当 k 减少时，右移位数的差会导致水平距离呈阶梯变化。我们只需检查 k 使得 levelA - k 和 levelB - k 变化时的边界点，大约 O(log n) 个候选。

具体：我们只需检查 k 使得 levelA - k 在 0..60 和 levelB - k 在 0..60 的边界，因为索引很大但右移超过 60 后差值最多为 1。

这样复杂度 O(log max_index)。

---

代码实现

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

typedef long long ll;

pair<int, ll> parse_path(const string& s) {
    int level = 0;
    ll index = 0;
    for (char c : s) {
        if (c == '1') {
            level++;
            index = index * 2;
        } else if (c == '2') {
            level++;
            index = index * 2 + 1;
        } else if (c == 'U') {
            level--;
            index = index / 2;
        } else if (c == 'L') {
            index--;
        } else if (c == 'R') {
            index++;
        }
    }
    return {level, index};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s1, s2;
    cin >> s1 >> s2;
    
    auto [levelA, indexA] = parse_path(s1);
    auto [levelB, indexB] = parse_path(s2);
    
    int min_level = min(levelA, levelB);
    ll ans = LLONG_MAX;
    
    // 检查 k 从 0 到 min_level 的某些关键点
    // 关键点：当右移位数差变化时
    // 简化：直接枚举所有 k，但用步长加速（因为水平距离变化缓慢）
    // 但数据大时，我们只检查 k 靠近 min_level 和几个边界
    
    // 优化：从 min_level 向下检查到 max(0, min_level - 60)
    int start = min_level;
    int end = max(0, min_level - 100); // 检查100层足够，因为右移超过60后水平差<=1
    
    for (int k = start; k >= end; --k) {
        int shiftA = levelA - k;
        int shiftB = levelB - k;
        ll ancestorA = indexA >> shiftA;
        ll ancestorB = indexB >> shiftB;
        ll dist = levelA + levelB - 2 * k + abs(ancestorA - ancestorB);
        if (dist < ans) ans = dist;
    }
    
    // 还要检查 k=0 的情况
    int k = 0;
    int shiftA = levelA - k;
    int shiftB = levelB - k;
    ll ancestorA = indexA >> shiftA;
    ll ancestorB = indexB >> shiftB;
    ll dist = levelA + levelB - 2 * k + abs(ancestorA - ancestorB);
    if (dist < ans) ans = dist;
    
    cout << ans << "\n";
    
    return 0;
}

---

算法标签

• 树结构导航
• 最低公共祖先（LCA）思想
• 二进制索引处理
• 最优层选择枚举

---