一道挺有意思的计数题，自己看洛谷题解不是很懂，max 讲了然后自己去看 AT 的题解就很易懂了。是好题，值得做！

然后就是你可能需要有一定耐心才能看得懂，但是这篇题解会尽可能详细地讲这道题。

upd on 2025.11.21 8:00：感谢 max 发现的一处微小错误。

首先我们可以换一种三元组的表达方式，考虑记录 $(x,a,b)$ 表示中间的点是 $x$，其两边分别间隔 $a,b$。考虑变化的过程，若钦定 $a<b$ 那么有 $(x,a,b)\to(x+a,a,b-a)$ 和 $(x,a,b)\to(x-a,b-a,a)$。我们考虑换一种更简洁清晰的表达方式，这里我使用了 AT 的图片：

这里我们省略了 $x$ 仅保留 $(a,b)$，然后将两种转化看成两条边，边权就是 $x$ 的变化量。于是我们统计不同的 $(x,a,b)$ 就变成了统计从根到图上每个点的路径数，可以发现两者恰好构成双射。进一步思考，一条边上有边权，那么对于一条从根开始的路径一定对应一个边权和。那么要统计到一个点的不同路径数，就相当于是统计边权和的情况数。计数的时候需要考虑不重不漏，所以我们需要找到一种合理的统计方式，在此之前我们可以先寻找图的性质。

我们设 $a_i$ 表示第 $i$ 次变化时中间的点的移动距离，也就是 $a_i$ 代表第 $i$ 列的边的边权的绝对值。考虑这个序列一种生成方式是在做辗转相减法的过程中记录较小的数，所以可以从这方面入手寻找性质。注意到在辗转相减的过程中我们会在某段时间减去相同的值，于是考虑把 $a_i$ 划分成 $\mathcal O(\log V)$ 个段。假设共有 $m$ 段，对于第 $i$ 段，我们假设有 $c_i$ 个 $b_i$，现在我们在 $b_i$ 上考虑。

这里有一个非常重要并且巧妙的性质：$b_i=c_{i+1}\times b_{i+1}+b_{i+2}(i\le m-2)$，就比如上图中有 $7=2\times3+1$。等式成立的原因可以考虑用辗转相除法优化辗转相减法的时候，有 $(a,b)\to (b,a\bmod b)$，这其实就是一个被除数 $=$ 除数 $\times$ 商 $+$ 余数的等式。注意这个性质在最后其实并不成立，因为最后一段的 1 全选就能凑出上一段的数，于是我们考虑手动去掉一个 1 保持性质。有了这个重要的性质之后现在考虑计数，我们先翻译一下这个结论，把它变成能够直接用的：选择了一个 $b_i$ 等价于选择了整段的 $b_{i+1}$ 以及一个 $b_{i+2}$。

那么我们考虑将所有的后者换成前者。当后者不能换成前者的时候说明第 $i$ 段已经全选了，以此类推，前 $i$ 段也已经全选了。说明我们一种边权和可以看成这样一种选择方案：选择了一个前缀 $i$ 满足第一段一直到第 $i$ 的所有数都已经全选，后面还有若干的 $b_j$ 被选择，但是如果选择了整段的 $b_j$ 就不能选择 $b_{j+1}$。

刻画出了选择方式我们就可以对此 dp 了。设 $f_{i,0/1}$ 表示考虑到了第 $i$ 段，在前缀全选的段不足 $i$ 的情况下这个段是否全选。转移是简单的，但这里还是负责任地讲一下。对于 $f_{i,0}$，考虑这一段从哪个状态转移，并且这一段选多少个数。于是有 $f_{i,0}=f_{i-1,1}+c_i\times(f_{i-1,0}+1)$。考虑如果上一段全选那么这一段不能选数；如果上一段不是全选那这一段可以选 $[0,c_i-1]$ 个数；如果全选的前缀是 $i$ 那么这一段能选 $[0,c_i-1]$ 个数。对于 $f_{i,1}$ 有 $f_{i,1}=f_{i-1,0}$，这是显然的。

最后我们考虑统计答案。对于一段的贡献一起统计，设 $s_i$ 表示第 $i$ 段的答案。考虑一个段 $i$ 最后一个位置 $j$ 的答案为 $f_{j,0}+f_{j,1}+1$，但是一个段中不同的位置其 $f_{j,0}$ 是不同的，因为 $f_{j,0}$ 与这个段的前缀长度有关。什么意思呢？就是说假设位置 $j$ 是第 $i$ 段的第 $k$ 个位置，我们转移 $f_{j,0}$ 的时候这个段能够选择的数其实只有 $[0,k-1]$，所以一个段中的 $f_{j,0}$ 略有不同，于是统计一个段的答案的时候就不能直接写 $c_i\times(f_{i,0}+f_{i,1}+1)$，而是去枚举段中的每个数，有：

把 $j$ 提出来化简即可。考虑最后的答案之和，根据上图，注意到除了最后一个段其他都有两个点，然后你还要考虑不做任何操作以及开头还有两个选择，并且前面去掉的那个 1 最后还会有贡献需要加回去，于是答案为 $3+\left(\sum_{i=1}^{m}2s_i\right)-2s_{m-2}-s_{m-1}$。最后时间复杂度为 $\mathcal O(q\log (c-a)$)。