1 条题解

  • 0
    @ 2026-2-17 18:22:03
    #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
    上传者