首先原题：

 

方法：

满二叉树，链长为logn

考虑枚举lca为x，两个链长h1,h2，

发现x是唯一确定的！

找到这个x，

s减去都走左儿子的贡献，再调整出右儿子

2^n-1->2^n，变成每一位的0/1更好算！只要知道选择了几个右儿子即可

然后数位DP

f[i][j][k]，i位，选了j个，有无从上一位来的进位

 

至于本题：

多了一个路径编号和

a，b的lca就是二进制下的lcp（从高位开始）

暴力枚举即可

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=53;ll mi[N],ans,f[N][2*N][2];ll d,a,b,c;ll calc(int h1,int h2,int us,ll p){ memset(f,0,sizeof f); f[0][0][0]=1; int tmp=log2(p); for(reg i=0;i
           
            >(i+1)&1; for(reg j=0;j<=us;++j){ for(reg k=0;k<=1;++k){ if(f[i][j][k]) for(reg a=0;a<=1;++a){ if(a==1&&(i+1)>h1) continue; for(reg b=0;b<=1;++b){ if(b==1&&(i+1)>h2) continue; if((a+b+k)%2!=now) continue; if(j+a+b>us) continue; f[i+1][j+a+b][(a+b+k)/2]+=f[i][j][k]; } } } } } return f[tmp][us][0];} ll wrk(ll s,int d){ // cout<<" wrk "<
            <<" d "<
             
              <
              
               d||ceng+h2>d) continue; tmp=(mi[h1+1]+mi[h2+1]-3)*x+mi[h2]-1; ll ret=s-tmp; if(ret<0||x<=0) break; if(ret==0) { ++ans;continue; } // cout<<" h1 "<
               
<<" h2 "<
               
<<" : "<
                
                 <<" "<
                 
                  <<" "<
                  
                   <
                   
                    >(d1-e))&1)==((b>>(d2-e))&1)){ lca=lca*2+((a>>(d1-e))&1);++e; } ll tmp=lca; dis=lca; // cout<<" lca "<
                    
                     <<" ee "<
                     
                      <
                      
                       >(d1-i))&1); dis+=tmp; } tmp=lca; for(reg i=e;i<=d2;++i){ tmp=tmp*2+((b>>(d2-i))&1); // cout<<" tmp "<
                       
                        <