同步发布于 here。
思路
神秘推式子题。
发现每个层的节点数和每个边的边权是随着深度的增加递增的，且存在公差 \(d=1\)，即其是一个等差数列，这个在我们后面需要用到。
题目询问 \(u,v\) 的最短距离，我们把每个节点 \(i\) 的深度设为 \(dep_i\)，令 \(dep_u \le dep_v\)，考虑两种情况：
- \(u\) 在 \(v\) 到节点 \(1\) 的路径上，则答案就是其中间的等差数列的和。
- \(u\) 不在 \(v\) 到节点 \(1\) 的路径上，其答案就是每个点到其 LCA 的权值的和，即两个等差数列的和。
发现其实判断 \(u\) 是否在 \(v\) 到 \(1\) 的路上，还是要求 LCA 的，所以我们就想怎么求 LCA。
发现其并不完全相同于一棵树，所以我们不能求其直接的 LCA，但是，我们发现，我们可以求 \(v\) 到 \(dep_u\) 深度时，所能到达的左右端点，可见，其中间所有的点都可以到达。
那么我们可以考虑 \(v\) 向上走走到 \(dep_u\) 时候的情况，发现若 \(u\) 在 \(v\) 能到达的区间 \([l,r]\) 中，即 \(l \le u \le r\) 时，答案就是 \(dep_u\) 到 \(dep_v\) 中间的边权的等差数列和，即 \(\sum_{i = dep_u} ^ {dep_{v} - 1} i\)。
若 \(u \le l\) 或 \(r \le u\) 时，可以发现，取最优的 LCA，同一深度的两个点就要尽可能的近，所以 \(v\) 就取 \(l\) 和 \(r\) 即可，其 LCA 就是一个一直向左上走，一个一直向右上走，直到这俩相遇，这也是个等差数列，只举 \(u \le l\) 的情况，其和为 \(\sum_{i = \max(dep_{u} - (l-u), 1)} ^ {dep_{u} - 1} i \times 2\) 其中乘二是因为要走两个相同长度的路。
上面的等差数列式子显然，根据所给图分析即可。
现在就只剩下两个问题：如何求深度且如何求这个区间。
求深度可以思考，我们其实是要解一个形似 \(x \times (x + 1) \ge v\) 的不等式，取相等，则 \(x = \left\lceil \frac{-1+\sqrt {1 + 8v}}{2} \right\rceil\)（负根被舍了） 可以发现因为精度我们是不准的，可能需要微调，这个用 while 即可，因为我们求的是近似确切值，所以 while 次数不会很多，时间复杂度约为 \(O(1)\)。
求区间，我们再次观察图，发现对于 \(v\)，其向左上走变成了 \(v - dep_v\) 了，其向右上走就变成了 \(v - (dep_v - 1)\) 了。可见，其走到 \(dep_u\) 也是一个等差数列，用等差数列求和得到向左右走的长度即可。
:::warning[注意边界]
注意我们理论上求得了 \(v\) 走到 \(dep_u\) 所能到的区间，但是我们的数学计算可能会使实际的 \(l,r\) 超出那个深度的边界编号，所以我们要与其边界编号分别取最大最小。
:::
代码
现在所有问题已经解决了，注意等差数列求和的起点，终点和个数即可，代码中我默认的是 \(dep_u \ge dep_v\)，注意不要搞混了。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll t, u, v;
ll calc(ll l, ll r, ll d){return (r + l) * d / 2;}
int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> t;while(t --){cin >> u >> v;if(u == v){cout << 0 << '\n';continue;}ll depu = ceil((-1 + sqrtl(1 + 8 * u)) / 2), depv = ceil((-1 + sqrtl(1 + 8 * v)) / 2), cnt = 0;while(depv * (depv + 1) / 2 < v) depv ++;while(depu * (depu + 1) / 2 < u) depu ++;//微调深度 if(depu < depv) swap(depu, depv), swap(u, v);//默认 u 的深度大 ll l = max(calc(1, depv - 1, depv - 1) + 1, u - calc(depv + 1, depu, depu - depv));ll r = min(calc(1, depv, depv), u - calc(depv, depu - 1, depu - depv));//求 u 到 depv 的能到的点的左右边界 cnt += calc(depv, depu - 1, depu - depv);//这是到 depv 所需的距离 if(l <= v && v <= r) {cout << cnt << '\n';continue;}// 若可以直接到达，就是这个距离 if(v > r) cnt += calc(max(depv - (v - r), 1ll), depv - 1, v - r) * 2; //否则就是两种情况，这里让 u=r else cnt += calc(max(depv - (l - v), 1ll), depv - 1, l - v) * 2;//这里让 u=l cout << cnt << '\n';}return 0;
}