1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量定义 int n , a , b; // n:树的总结点数;a、b:要求最短距离的两个目标结点 vector<int> arr[100100]; // 邻接表,存储树的无向边关系,arr[x]存放与x相连的所有结点 int fa[100100]; // 父节点数组,fa[i]记录结点i的父节点编号 int dep[100100]; // 深度数组,dep[i]记录结点i的深度(根节点深度为1) int wid[100100]; // 宽度统计数组,wid[len]记录第len层的结点总数 int max_len = 0; // 记录树的最大深度(即树的高度) // [2] 深度优先遍历DFS:遍历整棵树,完成3个核心任务 // 1. 计算每个结点的深度dep[x] // 2. 统计每层的结点数wid[len],更新树的最大高度max_len // 3. 记录每个结点的父节点fa[x] // 参数说明:x=当前遍历的结点;y=当前结点的父节点;len=当前结点的深度 void dfs(int x , int y ,int len) { dep[x] = len ; // 记录当前结点x的深度 wid[len]++; // 对应层数的结点计数+1,用于后续计算宽度 max_len = max( max_len , len); // 更新树的最大高度 fa[x] = y; // 记录当前结点x的父节点为y // [3] 遍历当前结点的所有邻接结点,递归访问子节点 for(int i = 0 ; i < arr[x].size() ; i++) { if(arr[x][i] == y) continue; // 跳过父节点,避免往回走导致死循环 dfs(arr[x][i] , x , len +1); // 递归遍历子节点,子节点深度+1 } } // [4] 求解两个结点的最近公共祖先LCA(Lowest Common Ancestor) // 参数说明:x、y为需要求LCA的两个结点,返回值为它们的最近公共祖先结点编号 int lca(int x , int y) { // [5] 第一步:将两个结点调整到同一深度 // 若y比x深,y不断向上移动到父节点,直到和x深度相同 while(dep[x] < dep[y]) { y = fa[y]; } // 若x比y深,x不断向上移动到父节点,直到和y深度相同 while(dep[x] > dep[y]) { x = fa[x]; } // [6] 第二步:两个结点同步向上移动,直到相遇,相遇点即为LCA while(x != y) { y = fa[y]; x = fa[x]; } return x; // 返回最近公共祖先结点编号 } int main() { // [7] 读取树的总结点数n cin >> n; // [8] 读取n-1条无向边,构建树的邻接表 for(int i = 1 ; i <= n - 1 ; i++) { int x , y; cin >> x >> y; arr[x].push_back( y ); // 把y加入x的邻接列表 arr[y].push_back( x ); // 把x加入y的邻接列表(无向边双向存储) } // [9] 读取要求最短距离的两个目标结点a和b cin >> a >> b; // [10] 父节点数组初始化(可选,后续DFS会覆盖所有结点的fa值,不影响结果) for(int i = 1 ; i <= n ; i++) fa[i] = i; // [11] 从根节点1开始DFS遍历整棵树,根节点的父节点设为自身,初始深度为1 dfs(1 , 1 , 1); // [12] 计算树的最大宽度:遍历所有层,取结点数的最大值 int max_wid=0; for(int i = 1 ; i <= n ; i++) max_wid = max( max_wid , wid[i]); // [13] 按输出格式,先输出树的高度、宽度 cout<< max_len << endl << max_wid << endl; // [14] 计算并输出a、b两点的最短距离,核心公式:dep[a]+dep[b]-2*dep[LCA(a,b)] cout<< dep[a] + dep[b] - 2 * dep[lca(a , b )]; return 0; }
- 1
信息
- ID
- 1080
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者