题解：P1797 【模板】Stern-Brocot 树

A6TVhmj · 2025-03-07 18:49:16 · 题解

这一道题其实实现难度并不高，主要考验数学知识。只要我们了解了 Stern–Brocot 树的性质，AC 这道题也就很容易了。

1. Stern–Brocot 树是什么

这是解出这一题的必备知识。Stern–Brocot 树是一种维护分数的优雅的结构，包含所有不同的正有理数。并且与连分数紧密相关，在算法竞赛中可以用于解决一系列的数论问题。

而这棵树按以下的方法构造：

Stern–Borcot 树可以在迭代构造第 k 阶 Stern–Brocot 序列的过程中得到。第 0 阶 Stern–Brocot 序列由两个简单的分数组成： \dfrac{0}{1} 和 \dfrac{1}{0}。(这里的 \dfrac{1}{0} 严格意义上并不算是有理分数，可以理解为表示 \infty 的最简分数。)

在第 k 阶 Stern–Brocot 序列相邻的两个分数 \dfrac{a}{b} 和 \dfrac{c}{d} 中间插入它们的中位分数，也就是 \dfrac{a+c}{b+d}，就得到第 k+1 阶 Stern–Brocot 序列。尽管中位分数的定义本身允许分数的约分，但是在 Stern–Brocot 树的构造中，只需要直接将分子和分母分别相加即可，而不必担心约分的问题。由此，可以迭代地构造出所有阶的 Stern–Brocot 序列。

将每次迭代中新添加的分数连结成树状结构，就得到了 Stern–Brocot 树。听上去有点懵，一图胜千言，下图就是前几层 Stern–Brocot 树的样子：

（图片来自oi-wiki）

Stern–Brocot 树还有几条性质：

最简性：Stern–Brocot 树上的所有分数都为既约分数。
单调性：Stern–Brocot 树的中序遍历单调递增。
完整性：Stern–Brocot 树不重不漏的包含了所有既约分数。

具体的数学证明可以在 oi wiki 上找到，接下来我重点讲一下几种询问的编程思路。

2. ENCODE_PATH 实现

首先是 ENCODE_PATH，也就是给定分数 \dfrac{p}{q}，查找从 Stern-Brocot 树根走到节点 \dfrac{p}{q} 的路径，刚刚我们说了，Stern–Borcot 树与连分数紧密相关的，怎么相关呢？来看下面的过程：

则设首组向右移动的次数为零。向右、向左交替移动端点，将每组移动后的端点位置排列如下：

\dfrac{p_0}{q_0},~\dfrac{p_1}{q_1},~\dfrac{p_2}{q_2},~\cdots,~\dfrac{p_{n-2}}{q_{n-2}},~\dfrac{p_{n-1}}{q_{n-1}},~\dfrac{p_n}{q_n}.

其中，偶数组移动是向右的，故而记录的是左端点的位置；奇数组移动是向左的，故而记录的是右端点的位置。在这一列端点前面再添加两个端点 \dfrac{p_{-2}}{q_{-2}}=\dfrac{0}{1} 和 \dfrac{p_{-1}}{q_{-1}}=\dfrac{1}{0}。设第 k 组移动的次数为 t_k，那么根据上面得到的移动次数与端点位置之间的关系可知 \dfrac{p_k}{q_k} = \dfrac{t_kp_{k-1}+p_{k-2}}{t_kq_{k-1}+q_{k-2}}。

如果连分数展开式 a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{\cdots+\dfrac{1}{a_n}}}} 用 [a_0,a_1,\cdots,a_n] 表示。那么，根据连分数的递推关系就可以知道，端点 \dfrac{p_k}{q_k} = [t_0,t_1,\cdots,t_k]。

而最后得到的连分数就是 \dfrac{p}{q} = \dfrac{p_k+p_{k-1}}{q_k+q_{k-1}} = [t_0,t_1,\cdots,t_{n-1},t_n,1]。

因此，在目标分数的末尾为一的连分数表示中，不计最后的一，前面的项就编码了 Stern–Brocot 树上自根节点到当前节点的路径。其中，偶数项（下标自 0 开始）是向右子节点的边，奇数项是向左子节点的边。所以树的查找用连分数实在是再好不过了。

代码如下：

void en(int x,int y){
    vector<pair<int, char>> res;
    bool right = true;//先向右走
    while(y){
        res.emplace_back(x / y, right ? 'R' : 'L');
        x %= y;
        swap(x, y);
        right ^= 1;//改变方向
    }//表达成连分数的形式
    res.back().first--;//连分数的最后一项减一
    if(res.front().first){
        printf("%d ",res.size());
        for(auto i=res.begin();i!=res.end();i++){
            printf("%c %d ",i->second,i->first);
        }
        return;
    }//res首项如果为{0,'R'}不输出。
    printf("%d ",res.size()-1);
    for(auto i=res.begin()+1;i!=res.end();i++){
        printf("%c %d ",i->second,i->first);
    }
}

3. ENCODE_PATH 实现

这一个询问就是反过来，知道路径输出分数。道理也是一样的，先把路径转换成连分数的形式，再把连分数转换成分数。但要注意的是，如果给出的路径是先往左走，那就得让首项为 0，因为连分数对应 Stern–Borcot 树总是先往右走的。加一个零就表示先不往右走，然后才往左走。

参照上文提到的连分数地推公式进行编写，核心代码如下：

void de(vector<int> a) {//a是连分数对应的数组，在此之前还要对路径进行上文的处理
    vector<int> p={0,1};
    vector<int> q={1,0};
    for (auto it:a) {
        p.push_back(p.back()*it+p.end()[-2]);
        q.push_back(q.back()*it+q.end()[-2]);
    }
    printf("%d %d ",p.back(),q.back());
}

这段代码在之后的询问中也会用到。

4. LCA 实现

同样根据上文将的原理，这其实就是求两个分数对应的两条路径的最长公共前缀对应的分数。思路就是按上文的方法先得到两个分数的路径，然后从前往后比较。例如样例中的 \dfrac{2}{3} 是 L1R1，\dfrac{3}{5} 是 L1R1L1。前面的 L1R1 是相同的，如果遇到不同的，方向相同则在公共路径末尾插入移动步数较少的，然后输出路径对应分数，相反则直接输出公共路径对应分数。如果像这里，一段路径已经比较完了也直接输出公共路径对应分数。代码如下：

void lca(int a,int b,int c,int d){
    vector<pair<int,char>> res1,res2;//两个分数对应的连分数
    bool right=1,flg=0;
    while(b){
        res1.emplace_back(a/b, right ? 'R' : 'L');
        a%=b;
        swap(a,b);
        right^=1;
    }
    res1.back().first--;
    right=1;
    while(d){
        res2.emplace_back(c/d,right?'R':'L');
        c%=d;
        swap(c,d);
        right^=1;
    }
    res2.back().first--;
    vector<int> r;//lca对应的连分数
    for(int i=0;i<min(res1.size(),res2.size());i++){
        if(res1[i].second!=res2[i].second)break;//方向不同停止
        else{
            r.push_back(min(res1[i].first,res2[i].first));
            if(res1[i].first!=res2[i].first)break;//移动步数不同也停止
        }
    }
    r.push_back(1);
    de(r);//把lca连分数转换成分数
}

5. ANCESTOR 实现

依然是用连分数的原理，在把分数转换成连分数路径时到 k 位就结束。如果路径长度比深度 k 小的话就输出 -1。举个例子，\dfrac{3}{5} 的路径可以用 LRL 表示，那深度为 2 的节点就是路径的前 2 位 LR。转换成连分数路径就是 L1R1，再把它转化成分数的形式就可以了（也就是 \dfrac{2}{3}）。

代码如下：

void anc(int k,int a,int b){
    string res;
    if(a+b>2){
        bool right=1,flg=0;
        while(b){
            for(int i=0;i<a/b;i++){
                res+=right ? 'R' : 'L';
                if(res.size()>k){
                    flg=1;
                    break;
                }//深度超过k了就退出
            }
            a%=b;
            swap(a,b);
            right^=1;
            if(flg)break;
        }
        res.pop_back();
    }
    if(res.size()<k){
        cout<<-1;return;
    }
    string s=res.substr(0,k);//取前k位路径
    vector<int>r={0};
    char x='R';
    for(int i=0;i<s.size();i++){
        if(s[i]==x)r.back()++;
        else {
            r.push_back(1);
            x=s[i];
        }
    }
    r.push_back(1);//转换成de函数可以处理的形式
    de(r);
}

6. RANGE 实现

这个询问其实就是在问这个分数在构建树的时候，\dfrac{p}{q} 是在哪两个分数中间插入的，所以可以用 Stern–Brocot 树本身的性质去做。从构建方法入手，我们可以发现，如果要查找的分数 \dfrac{p}{q} 落入 \dfrac{a}{b} 和 \dfrac{c}{d} 之间，那么连续 t 次向右移动时，右侧边界保持不动，而左侧节点移动到 \dfrac{a+tc}{b+td} 处；反过来，连续 t 次向左移动时，左侧边界保持不动，而右侧节点移动到 \dfrac{ta+c}{tb+d} 处。

因此，可以直接通过 \dfrac{a+tc}{b+td}<\dfrac{p}{q} 或 \dfrac{p}{q}<\dfrac{ta+c}{tb+d} 来确定向右和向左移动的次数。而如果 \dfrac{p}{q} 刚好是 \dfrac{a}{b} 和 \dfrac{c}{d} 的中位分数，那 \dfrac{a}{b} 和 \dfrac{c}{d} 就是我们要找到。最后还要注意题目中的两个特判：\dfrac{0}{1} 和 \dfrac{1}{0}。

代码如下：

void ran(int x,int y){
    if(x==1&&y==0){
        cout<<"1 0";
        return;
    }else if(x==0&&y==1){
        cout<<"0 1";
        return;
    }//两个特判
    int a=0,b=1,c=1,d=0;
    bool right = true;
    while(x!=a+c||y!=b+d){//寻找两个分数
        if(right){//决定移动方向
          auto t = (b*x-a*y-1)/(y*c-x*d);
          a+=t*c;
          b+=t*d;//缩小范围，下同
        }else{
          auto t=(y*c-x*d-1)/(b*x-a*y);
          c+=t*a;
          d+=t*b;
        }
        right^=1;
    }
    printf("%d %d %d %d",a,b,c,d);
}

7. 完整程序

最后把所有询问功能组合起来再加上输入、输出和一部分处理就是完整程序了，注释可以看前面。

码风偏差，请多多见谅。

#include<bits/stdc++.h>
using namespace std;
void en(int x,int y){
    vector<pair<int,char>> res;
    bool right = true;
    while(y){
        res.emplace_back(x/y,right?'R':'L');
        x%=y;
        swap(x,y);
        right^=1;
    }
    res.back().first--;
    if(res.front().first){
        printf("%d ",res.size());
        for(auto i=res.begin();i!=res.end();i++)printf("%c %d ",i->second,i->first);
        return;
    }
    printf("%d ",res.size()-1);
    for(auto i=res.begin()+1;i!=res.end();i++){
        printf("%c %d ",i->second,i->first);
    }
}
void de(vector<int> a) {
    vector<int> p={0,1},q={1,0};
    for (auto it:a) {
        p.push_back(p.back()*it+p.end()[-2]);
        q.push_back(q.back()*it+q.end()[-2]);
    }
    printf("%d %d ",p.back(),q.back());
}
void lca(int a,int b,int c,int d){
    vector<pair<int,char>> res1,res2;
    bool right=1,flg=0;
    while(b){
        res1.emplace_back(a/b, right ? 'R' : 'L');
        a%=b;
        swap(a,b);
        right^=1;
    }
    res1.back().first--;
    right=1;
    while(d){
        res2.emplace_back(c/d,right?'R':'L');
        c%=d;
        swap(c,d);
        right^=1;
    }
    res2.back().first--;
    vector<int> r;
    for(int i=0;i<min(res1.size(),res2.size());i++){
        pair<int,char> m=res1[i],n=res2[i];
        if(m.second!=n.second)break;
        else{
            r.push_back(min(m.first,n.first));
            if(m.first!=n.first)break;
        }
    }
    r.push_back(1);
    de(r);
}
void anc(int k,int a,int b){
    string res;
    if(a+b>2){
        bool right=1,flg=0;
        while(b){
            for(int i=0;i<a/b;i++){
                res+=right?'R':'L';
                if(res.size()>k){
                    flg=1;
                    break;
                }
            }
            a%=b;
            swap(a,b);
            right^=1;
            if(flg)break;
        }
        res.pop_back();
    }
    if(res.size()<k){
        printf("-1");return;
    }
    string s=res.substr(0,k);
    vector<int>r={0};
    char x='R';
    for(int i=0;i<s.size();i++){
        if(s[i]==x)r.back()++;
        else {
            r.push_back(1);
            x=s[i];
        }
    }
    r.push_back(1);
    de(r);
} 
void ran(int x,int y){
    if(x==1&&y==0){
        printf("1 0");
        return;
    }else if(x==0&&y==1){
        printf("0 1");
        return;
    }
    int a=0,b=1,c=1,d=0;
    bool right = true;
    while(x!=a+c||y!=b+d){
        if(right){
          auto t = (b*x-a*y-1)/(y*c-x*d);
          a+=t*c;
          b+=t*d;
        }else{
          auto t=(y*c-x*d-1)/(b*x-a*y);
          c+=t*a;
          d+=t*b;
        }
        right^=1;
    }
    printf("%d %d %d %d",a,b,c,d);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        char s[1000],tmp;int x,y;
        string k;
        cin>>k>>x;
        if(k=="DECODE_PATH"){
            vector<int> r;
            bool first=1;
            while(x--){
                cin>>tmp>>y;
                if(first && tmp=='L'){r.push_back(0);}
                first=0;
                r.emplace_back(y);
            }
            r.push_back(1);//路径转连分数 
            de(r);
        }else if(k=="ENCODE_PATH"){
            scanf("%d",&y);
            en(x,y);
        }else if(k=="LCA"){
            int z,a;
            scanf("%d%d%d",&y,&z,&a);
            lca(x,y,z,a);
        }else if(k=="ANCESTOR"){
            int z;
            scanf("%d%d",&y,&z);
            anc(x,y,z);
        }else{
            scanf("%d",&y);
            ran(x,y);
        }
        putchar('\n');
    }
    return 0;
}

注:部分代码借鉴自 oi-wiki。