2025-2026 ICPC NERC, Kyrgyzstan Regional Contest 吉尔吉斯斯坦——I. Cutting Trees（这种题目呢，显然是需要你去观察得到一个结论。但是怎么样去观察呢？往往这些题目具有自相似的这个特性，因此我们可以从一层开始，先只考虑一层，然后再考虑下面一层，分层的去解决这个问题） · znzryb
## 题目大意
- **第 1 棵树**：仅包含节点 $1$。
- **第 2 棵树**：加入节点 $2$ 并与节点 $1$ 相连，根节点为 $2$。
- **第** $n$ **棵树的构建（由第** $n-1$ **棵树生成）**：
1. 从第 $n-1$ 棵树的**根节点**出发，向下寻找一条通往叶子节点的路径。在每一步选择子节点时，总是选择**编号最大**的那个子节点。
1. **删除**该路径上原有的所有边。
1. 加入编号为 $n$ 的新节点，将 $n$ 与刚才路径上的**每一个**节点分别用一条边相连。
1. 节点 $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)$。
1. **T3**：T2 路径为 $2 \to 1$。删除 $(2,1)$。加入 $3$，连接 $(3,2), (3,1)$。根 $3$。
1. **T4**：T3 根 $3$，子节点 $\{2, 1\}$，最大子节点 $2$（叶子）。路径 $3 \to 2$。删除 $(3,2)$。加入 $4$，连接 $(4,3), (4,2)$。保留 $(3,1)$。根 $4$。
1. **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$。
1. **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$。
1. **查询**：在 T6 中从 $6$ 到 $1$。由于 $6$ 直接连接 $5$，且 $5$ 此时保留了与 $1$ 的连接（$(5,1)$ 在生成 T6 时未被选中删除），路径为 $6 \to 5 \to 1$。
1. **结果**：$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 加二位以及以后的位，它的这个情况。
```cpp
// 判断 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 函数，就可以非常轻松的求解这个东西了。
```cpp
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](https://codeforces.com/gym/106169/submission/363673850)
::: 源代码
```cpp
/**
* 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;
}
/*
*/
```
:::