1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量:n为树的总结点数,a、b为冗余未使用变量 int n , a , b; // [2] 邻接表,存储树的无向边,arr[x]存放与结点x相连的所有结点 vector<int> arr[100100]; // [3] 父节点数组,冗余未使用 int fa[100100]; // [4] 结点深度数组,冗余未使用 int dep[100100]; // [5] 层宽度统计数组,冗余未使用 int wid[100100]; // [6] 全局变量,记录树的直径(树中最长路径的边数)的最大值 int max_len = 0; // [12] 树形DP核心函数:计算以x为根的子树中,x向下延伸的最长路径长度,同时更新全局直径最大值 // 参数说明:x=当前遍历的结点,y=当前结点的父结点(用于避免往回走,防止死循环) int dfs(int x , int y) { // [13] 定义变量:first_len记录当前结点向下的最长路径长度,second_len记录第二长路径长度 int first_len = 0 , second_len = 0; // [14] 遍历当前结点的所有邻接结点,递归处理子结点 for(int i = 0 ; i < arr[x].size() ; i++) { // [15] 跳过父结点,避免往回遍历导致死循环 if(arr[x][i] == y) continue; // [16] 递归计算子结点向下的最长路径长度,+1是当前结点到子结点的这条边的长度 int len = dfs( arr[x][i] , x) + 1; // [17] 更新当前结点的最长、第二长路径长度 if( len >= first_len) { second_len = first_len; // 原最长路径降级为第二长 first_len = len; // 更新最长路径 }else if(len > second_len) { second_len = len; // 新路径小于最长但大于第二长,更新第二长 } } // [18] 经过当前结点的最长路径=最长子路径+第二长子路径,更新全局直径最大值 int zhijin = first_len + second_len; max_len = max(max_len , zhijin); // 返回当前结点向下的最长路径长度,供父结点计算使用 return first_len; } int main() { // [7] 读取树的总结点数n cin >> n; // [8] 循环读取n-1条无向边,构建树的邻接表 for(int i = 1 ; i <= n - 1 ; i++) { // [9] 读取当前边的两个端点x、y int x , y; cin >> x >> y; // [10] 无向边双向存储,将两个端点互相加入对方的邻接列表 arr[x].push_back( y ); arr[y].push_back( x ); } // [11] 调用dfs函数,从根结点1开始执行树形DP,父结点设为0(不存在的结点,避免回走) dfs(1 , 0); // [19] 输出最终计算得到的树的直径 cout << max_len; return 0; }
- 1
信息
- ID
- 1081
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者