1 条题解

  • 0
    @ 2026-2-17 21:45:10
    #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
    上传者