1 条题解

  • 0
    @ 2026-2-17 13:12:45
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] n:树的结点总数;r:指定的根结点编号
    int n , r;
    // [2] 邻接表数组,存储树的无向边,arr[x]保存与结点x直接相连的所有结点
    vector<int> arr[100100]; 
    // [3] depth[x]存储结点x在树中的深度
    int depth[100100];
    
    // [8] 深度优先搜索:遍历整棵树,递归计算每个结点的深度
    // 参数x:当前结点;参数y:当前结点的父结点(避免往回遍历)
    void dfs(int x , int y)
    {
        // [9] 遍历当前结点x的所有相邻结点
        for(int i = 0 ; i < arr[x].size() ; i++)
        {
            // [10] 若相邻结点是父结点,跳过以避免死循环
            if(arr[x][i] == y) continue;
            // [11] 子结点深度 = 当前父结点深度 + 1
            depth[arr[x][i]] = depth[x] + 1;
            // [12] 递归访问子结点
            dfs(arr[x][i] , x);
        }
    }
    
    int main()
    {	
        // [4] 读入总结点数和根结点编号
        cin >> n >> r;
        // [5] 构建树的邻接表
        for(int i = 1 ; i <= n - 1 ; i++)
        {
            int x , y;
            cin >> x >> y;
            arr[x].push_back( y );
            arr[y].push_back( x );
        }
        
        // [6] 初始化根结点深度为1
        depth[r] = 1;
        // [7] 从根结点开始DFS计算深度
        dfs(r , 0); 
        
        // [13] 处理询问
        int q;
        cin >> q;
        
        vector<int> a(q+1);
        // [14] 读入所有询问
        for(int i = 1 ; i <= q ; i++)
            cin >> a[i]; 
        
        // [15] 按顺序输出答案
        for(int i = 1 ; i <= q ; i++)
            cout <<  depth[a[i]] << endl;
        
        return 0;                  
    }
    
    • 1

    信息

    ID
    1070
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    2
    已通过
    1
    上传者