虽然我不知道为什么我写得这么短还跑这么快

首先观察这棵树,发现每个点一定是尽量往上跳。

我们把每个点的标号加一，这样每个点的标号的二进制就同时表示了从根到这个点的路径。

每次从一个节点走到一个儿子,如果是左儿子就在标号的最低位前添加一个0,右儿子就添加一个1。

考虑让询问的点同时向上跳,最后在两点LCA处会和。

如下图,红色的行走方案对应了绿色的跳跃过程。

考虑对于每个点$x$,求它通过一个块可以跳到的最高的点,定义为$Find(x)$。

定义某棵子树根节点两侧的块为外面的块,下方的块为里面的块。注意定义是相对的,以下里/外面的块都定义在某一相同子树中。

如果这棵子树中的一个节点与根之间的路径一直是同一方向,或者说这个节点的编号,去掉与子树根相同的一段前缀后,剩下的部分全0或全1,那么这两点就与同一个外面的块相邻。

比如上图中点8和点2,二进制表示分别为1000和10,点2到点8的路径就可以表示为00;

而点15和点1,二进制表分别为1111和1,点1到点15的路径就可以表示为111。

同理,如果这棵子树中的一个节点与根之间的路径中,只有最后一条边与其他边方向不同,或者说去掉与子树根相同的一段前缀后,剩下的部分除最高位外相同,最高位不同,那么这两点就与同一个里面的块相邻。

比如上图中点12和点1,二进制表示分别为1100和1,点1到点12的路径就可以表示为100。

那么,对于一个点,通过外面的块可以到达的最远的节点的编号就是删去该节点编号中最长的一段相同后缀后的值。

而通过里面的块可以到达的最远的节点就是在上面的基础上再再末尾删去一位后得到的。

显然后者的位置更高。注意如果这个节点编号为0,那么事实上你最高只能到达1。

再回来考虑一次询问$A,B$。

首先求出两者的$LCA$,设为$t$。

两边分别跳,以节点$A$为例。

首先令$A=Find(A)$,如果$A\le t$,那么已经到达,结束。

否则我们还需要继续向上,那么需要穿过某一条边然后继续跳,答案加一。

两侧答案相加即可。

做完了?

还没有。

考虑下图中的点8和15,$LCA$为1,两边向上跳得到的答案都是0。但是答案显然是1。

(懒得重画,搬了上面那张)

为什么?

因为事实上两点向上跳到1后,还是在两个不同的块中。

此时答案要加1。

那什么时候要加1呢?

事实上,当我们通过某个块到达最高的点$x$,一定是通过了$x$为根的子树中里面的块(除非$x=1$,想想为什么)。

那么到达$x$后,我们可以选择穿过某条边,从而进入$x$这棵子树的某个外面的块。其中一个在$x$的父亲的子树中是里面的块,另一个还是外面的块。

那么,我们具体跳哪个呢?

首先如果$Find(x)> t$,那么跳哪边决定于哪边能到达最高的点,不需要考虑。

当$Find(x)\le t$,那么$x$和$t$一定与某个共同的块相邻。

在大部分情况下,$x$只和$t$子树中一个里/外面的块相邻。这个时候选择是唯一的,你不可能多走一步来得到更优的方案。

但是有两个点的情况例外,那就是$t$的两个子节点。

事实上,此时一定是跳$t$子树的里面的块更优。

为什么呢?(可以先自己想一想)

下面给出证明:

由于$t$是两点的$LCA$,所以询问中的两个点一定分别在$t$的两个孩子的子树中。

在$t$的两个孩子的位置,可以往里跳或往外跳。

这两个孩子的子树中都有一个需要考虑的节点。

如果一个节点不是这两个孩子中的一个,那么它的跳跃方案是固定的。

如果这个节点是某一个孩子:

如果这个孩子向里跳,另一侧的点可能跳到$t$子树中里面的块,此时答案不用+1。

如果这个孩子向外跳,另一边的点会跳到$t$子树中里面的块或者外面的块,但是由于两个点在不同的子树中,所以跳到的外面的块是不同的块,此时答案必须+1。

所以往里跳更优。

然后再回到问题。两侧都有一个需要考虑的点。考虑一侧,计这个点为$lst$。

如果最后让$lst$往里跳,计$p=0$,否则$p=1$。

如果$lst$不是$t$的孩子,那么直接判断,判断过程类似于之前计算$Find$的过程,看看二进制中$lst$去除与$t$相同的前缀之后的部分是否只有一种数即可,如果只有一种数,令$p=1$,否则$p=0$。

如果$lst$是$t$的孩子,那么直接令$p=0$。

那么最后,答案需要加上$p_1\ or\ p_2$。

注意一种特殊情况,如果一开始询问给出的点有祖孙关系,那么答案无论如何不需要+1。

时间复杂度$O(T\log(A+B))$。

具体实现见代码。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T,ans,p1,p2;
ll a,b,lst,t,tmp,ret;
ll LCA(ll x,ll y){
    while(x!=y)x>y?x>>=1:y>>=1;
    return x;
}
ll Find(ll x){
    tmp=(x&1);
    while((x&1)==tmp)x>>=1;//消去一段相同的
    return max(1ll,x>>1);//然后再消去一位
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&a,&b),++a,++b,t=LCA(a,b),ans=lst=p1=p2=0;
        while(a>t)lst=a,a=Find(a),ans+=a>t;
        if(!lst)p1=-1;//a就是lca
        else if(((t<<1)|(lst&1))==lst)p1=0;//lst与t是父子关系
        else{
            tmp=lst&1,p1=1;
            while(lst!=t)p1&=((lst&1)==tmp),lst>>=1;//看去除相同前缀后剩余部分每一位是否相同
        }
        lst=0;
        while(b>t)lst=b,b=Find(b),ans+=b>t;
        if(!lst)p2=-1;
        else if(((t<<1)|(lst&1))==lst)p2=0;
        else{
            tmp=lst&1,p2=1;
            while(lst!=t)p2&=((lst&1)==tmp),lst>>=1;
        }
        printf("%d\n",ans+(p1!=-1&&p2!=-1?(p1||p2):0));
    }
    return 0;
}