1 条题解

  • 0
    @ 2026-1-27 19:20:17
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,x,y;               // [1] n-树的节点总数;x、y-需要计算最近公共祖先的两个目标节点
    int arr[110];            // [2] arr数组-存储每个节点的父节点(下标为节点编号,值为父节点编号)
    int brr[110]={};         // [3] brr数组-记录节点在x和y的路径上出现的次数(初始化为0)
    
    // 递归函数:标记从节点c到根节点的路径上的所有节点
    void f(int c){
        brr[c]++;            // [4] 标记当前节点c在路径上出现一次
        if(arr[c] == c) return; // [5] 如果当前节点是根节点(父节点是自己),递归终止
        else f(arr[c]);      // [6] 否则递归向上,标记父节点的路径
    } 
    
    int main(){
        cin>>n>>x>>y;        // [7] 读取节点总数n和两个目标节点x、y
        // 初始化:假设每个节点的父节点是自己(根节点的父节点就是自身)
        for(int i=1;i<=n;i++) arr[i]=i; // [8] 初始化父节点数组,每个节点初始父节点为自身
        
        // 读入父节点关系,更新arr数组
        int a,b;
        for(int i=1;i<n;i++){
            cin>>a>>b;
            arr[a]=b;        // [9] 记录节点a的父节点为b
        }
        
        brr[x]++,brr[y]++;   // [10] 特殊处理:先标记x和y本身在路径上出现一次
        // 从x和y的父节点出发,递归标记到根的路径
        f(arr[x]);           // [11] 递归标记x的父节点到根的路径上的所有节点
        f(arr[y]);           // [12] 递归标记y的父节点到根的路径上的所有节点
        
        // 寻找最近公共祖先:遍历所有节点(从n到1),找到第一个出现两次的节点
        for(int i=n;i>=1;i--){
            if(brr[i]==2){   // [13] 找到在x和y路径上都出现过的节点(公共节点)
                cout<<i;     // [14] 输出最近公共祖先(从大到小遍历,第一个找到的就是深度最大的公共节点,即最近的)
                break;
            }
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1077
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者