1 条题解
-
0
#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
- 上传者