1 条题解
-
0
#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
- 上传者