2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——I. Cutting Trees（这种题目呢，显然是需要你去观察得到一个结论。但是怎么样去观察呢？往往这些题目具有自相似的这个特性，因此我们可以从一层开始，先只考虑一层，然后再考虑下面一层，分层的去解决这个问题）

题目大意

• 第 1 棵树：仅包含节点 $1$。

• 第 2 棵树：加入节点 $2$ 并与节点 $1$ 相连，根节点为 $2$。

• 第 $n$ 棵树的构建（由第 $n-1$ 棵树生成）：

  1. 从第 $n-1$ 棵树的根节点出发，向下寻找一条通往叶子节点的路径。在每一步选择子节点时，总是选择编号最大的那个子节点。
  2. 删除该路径上原有的所有边。
  3. 加入编号为 $n$ 的新节点，将 $n$ 与刚才路径上的每一个节点分别用一条边相连。
  4. 节点 $n$ 成为第 $n$ 棵树的新根。

问题描述

给定两个整数 $n$ 和 $v$（$1 \le v \le n \le 10^{18}$），请计算在第 $n$ 棵树中，从根节点（节点 $n$）到节点 $v$ 的最短路径上，所有经过节点的编号之和（包含起点 $n$ 和终点 $v$）。

输入格式

一行包含两个整数 $n$ 和 $v$。

输出格式

输出一个整数 $S$，表示路径节点编号之和。

样例数据

Input
2 1
Output
3

Input
3 2
Output
5

Input
6 1
Output
12

Input
9 6
Output
23

样例解释

以 6 1 为例（输出 12）：

1. T2：根 $2$，边 $(2,1)$。

2. T3：T2 路径为 $2 \to 1$。删除 $(2,1)$。加入 $3$，连接 $(3,2), (3,1)$。根 $3$。

3. T4：T3 根 $3$，子节点 $\{2, 1\}$，最大子节点 $2$（叶子）。路径 $3 \to 2$。删除 $(3,2)$。加入 $4$，连接 $(4,3), (4,2)$。保留 $(3,1)$。根 $4$。

4. T5：T4 根 $4$，子节点 $\{3, 2\}$，最大子节点 $3$（$3$ 连 $1$）。路径 $4 \to 3 \to 1$。删除 $(4,3), (3,1)$。加入 $5$，连接 $(5,4), (5,3), (5,1)$。保留 $(4,2)$。根 $5$。

5. T6：T5 根 $5$，子节点 $\{4, 3, 1\}$，最大子节点 $4$（$4$ 连 $2$）。路径 $5 \to 4 \to 2$。删除 $(5,4), (4,2)$。加入 $6$，连接 $(6,5), (6,4), (6,2)$。保留 $(5,3), (5,1)$。根 $6$。

6. 查询：在 T6 中从 $6$ 到 $1$。由于 $6$ 直接连接 $5$，且 $5$ 此时保留了与 $1$ 的连接（$(5,1)$ 在生成 T6 时未被选中删除），路径为 $6 \to 5 \to 1$。

7. 结果：$6 + 5 + 1 = 12$。

思路讲解

AI 提示 1

这道题的关键在于发现树的递归自相似结构。让我带你一步步找到规律。
观察一：根的孩子有什么规律？
把每棵树根节点的孩子列出来：

• $T_2$：孩子 = $\{1\}$
• $T_3$：孩子 = $\{2, 1\}$
• $T_4$：孩子 = $\{3, 2\}$
• $T_5$：孩子 = $\{4, 3, 1\}$
• $T_6$：孩子 = $\{5, 4, 2\}$
• $T_9$：孩子 = $\{8, 7, 5, 1\}$
  规律：根 $n$ 的孩子恰好是 $n-1, n-2, n-4, n-8, \ldots$（即 $n - 2^j$，直到减出的值 $\le 0$）。这可以通过分析最大子节点路径来证明——该路径恰好经过 $n-1, n-2, n-4, \ldots$。
  观察二：子树的自相似结构
  第 $j$ 个孩子 $c_j = n - 2^j$ 的子树里，所有节点等间距排列，间距为 $2^{j+1}$。例如在 $T_9$ 中：
• 孩子 $8$（$j=0$）的子树：$\{8, 6, 4, 2\}$，间距 $2$
• 孩子 $7$（$j=1$）的子树：$\{7, 3\}$，间距 $4$
• 孩子 $5$（$j=2$）的子树：$\{5\}$，间距 $8$
  而且每个子树的内部结构和某个更小的 $T_m$ 完全同构！
  观察三（核心）：如何判断 $v$ 在哪个子树里？
  计算 $d = n - v$，然后求 $d$ 的二进制末尾零的个数 $j = \nu_2(d)$，$v$ 就在第 $j$ 个孩子 $n - 2^j$ 的子树中。
  验证（$T_9$ 中）：
• $v=6$：$d=3=11_2$，$j=0$ → 在孩子 $8$ 的子树 ✓
• $v=3$：$d=6=110_2$，$j=1$ → 在孩子 $7$ 的子树 ✓
• $v=1$：$d=8=1000_2$，$j=3$ → 在孩子 $1$ 的子树 ✓
  观察四：递归下降求路径
  进入子树后，"根"变为 $c_j$，"步长"变为 $b \cdot 2^{j+1}$，然后重复同样的过程。每一步步长至少翻倍，所以总共只需 $O(\log n)$ 步。
  整个算法伪代码：

sum = n, r = n, b = 1
while v ≠ r:
    d = (r - v) / b
    j = ν₂(d)       // d 的末尾零个数
    next = r - b × 2^j
    sum += next
    b ← b × 2^(j+1)
    r ← next
输出 sum

手动跑一下样例 9 6：

• $r=9, b=1$：$d=3, j=0$，下一步 $8$，$b \leftarrow 2$，sum$=17$
• $r=8, b=2$：$d=1, j=0$，下一步 $6$，$b \leftarrow 4$，sum$=23$
• $r=6=v$，输出 $23$ ✓
  时间复杂度 $O(\log n)$，完全可以处理 $10^{18}$。

AI 说的实在是，怎么说呢？讲的不是说很好啊，这 AI 讲的不是说很好，所以我认为真正的 AGI 啊，真正的 AGI 肯定是要会画图的。啊，现在的这个 AI 这个画图能力 比较一言难尽吧。

哎，不扯了，我们来看看这道题目。这道题目的规律，我这样子画了一张图啊，我觉得就很明显了。这就是所谓 AI 口中的自相似。你要说是自相似也也没什么问题，但是呢，自相似，但又没有那么相似。首先要注意到，根节点的孩子是 N 减一、 N 减二、 N 减四、 N 减八、 N 减十六。云云。这个注意到还是有一定难度啊，还是有一定难度，因为他毕竟哎，毕竟他不是一个这个线性的规律，对吧？

然后你注意到这个规律以后呢，你可以把这个规律应用于下面的节点，它们的孩子节点是怎么样子的。我们会发现，如果说这个根节点是 N 减一，那么令 N 减一等于 N 那么它的叶子节点，它的孩子节点就是 N 撇减二、 N 撇减四、 N 撇减八。如果令 N 撇减二等于 N 撇撇。那么它的孩子节点就是 N 撇撇减四。

好，现在的问题就来到什么呢？你注意到了这个规律，要写一个程序，在 LogN 的时间复杂度内求解。

注意啊，就是减法非常难以考虑。你去减法的话，你就会发现，哎，他怎么退位呀，进位呀，反正反正很难考虑。但是不妨反过来想。我们是要判断一一个点，就这个数在哪棵子树内。那我们就想，它能不能通过某种方法去加到它的根，对吧？去加回到它的根。加法比减法好想的多。

究其原因呢，加法比减法好想，其实是因为减法它会影响其后面的位，加法只会影响它前面的位。减法的这种回退的特性是我们最讨厌的。

判断的逻辑如此书写即可。不难发现的，我们实际上就是想要查看后 CI +1 位它的这个是否一样。之所以查看的是后 CI 加一位，是因为加法它只能改变 CI 加二位以及以后的位，它的这个情况。

// 判断 V 属不属于 u,ci 的这个子树。
auto check=[&](ll u,ll ci) -> bool {
  // 查看后 CI +1 位它的这个是否一样，所需要的 mask。
    ll mask=(1ll<<(ci+1))-1;
    // 直接进行与运算以后，就得到了 V 的后 CI +1 位，以及 U 的后 CI +1 位。
    ll a=mask&V,b=mask&u;
    if (a==b) {
        return true;
    }
    return false;
};

有了这个 check 函数以后，我们就写一个递归式的 solve 函数，就可以非常轻松的求解这个东西了。

auto solve=[&](auto && self,ll u,ll ci) -> void {
    ans+=u;
    if (u==V) {
        return;
    }
    for (ll j=ci+1;;j++) {
        ll to=u-(1ll<<j);
        if (to<=0) {
            break;
        }
        // 下面我们就是要判断我们想求的 V 到底在哪个子树之中呢？
        // 严格来讲，其实是判断 V 属不属于 to 的这个子树。
        if (check(to,j)) {
            self(self,to,j);
            break;
        }
    }
};

AC代码

哎呀，这个 CF 挂的。今天是2月20号，这 CF 还是在，就是已经挂了5个多小时了。那么AI 我让 AI 对拍了一下这个程序是对的。啊，他拍了2000多组数据，都没发现这个 hack 那么这个应该就是对的。这个我这个也是一遍写出来的，挺爽的。

AC

https://codeforces.com/gym/106169/submission/363673850

源代码

/**
 * Problem: I. Cutting Trees
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106169/problem/I
 * Created: 2026-02-19 23:02:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
void Solve() {
    ll N,V;
    cin >> N >> V;
    ll ans=0;
    // 判断 V 属不属于 u,ci 的这个子树。
    auto check=[&](ll u,ll ci) -> bool {
        ll mask=(1ll<<(ci+1))-1;
        ll a=mask&V,b=mask&u;
        if (a==b) {
            return true;
        }
        return false;
    };
    auto solve=[&](auto && self,ll u,ll ci) -> void {
        ans+=u;
        if (u==V) {
            return;
        }
        for (ll j=ci+1;;j++) {
            ll to=u-(1ll<<j);
            if (to<=0) {
                break;
            }
            // 下面我们就是要判断我们想求的 V 到底在哪个子树之中呢？
            // 严格来讲，其实是判断 V 属不属于 to 的这个子树。
            if (check(to,j)) {
                self(self,to,j);
                break;
            }
        }
    };
    solve(solve,N,-1);
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*

*/