1 条题解
-
0
#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> using namespace std; const int MAXN = 10005; vector<int> t[MAXN]; // 存储树的邻接表 int n, x; // n 为节点数,x 为藏宝节点 int node_count[MAXN]; // 存储每个子树的节点数 // 计算每个子树的节点数 void dfs_count(int node, int parent) { node_count[node] = 1; // 计入当前节点 for (int child : t[node]) { if (child != parent) { dfs_count(child, node); node_count[node] += node_count[child]; // 累加子节点的数量 } } } // 按照规则遍历树并计算访问节点数 int dfs_traverse(int node, int parent, int target, unordered_set<int>& visited) { visited.insert(node); int count = 1; if (node == target) { return count; // 找到宝藏,返回已访问节点数 } vector<int> children; for (int child : t[node]) { if (child != parent) { children.push_back(child); } } if (children.size() == 2) // 如果有两个子节点 { // 按照子树节点数来排序 sort(children.begin(), children.end(), [](int a, int b) { return node_count[a] < node_count[b]; }); } // 遍历子节点 for (int child : children) { if (visited.find(child) == visited.end()) { count += dfs_traverse(child, node, target, visited); if (visited.find(target) != visited.end()) { return count; } } } visited.erase(node); return count; } int main() { while (cin >> n >> x) { // 清空树和节点计数 for (int i = 1; i <= n; ++i) { t[i].clear(); } // 读取树的结构 for (int i = 1; i <= n; ++i) { int k; cin >> k; for (int j = 0; j < k; ++j) { int child; cin >> child; t[i].push_back(child); } } // 计算每个子树的节点数 dfs_count(1, -1); // 访问节点并计算访问的总节点数 unordered_set<int> visited; int result = dfs_traverse(1, -1, x, visited); cout << result << endl; } return 0; }
信息
- ID
- 135
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 13
- 已通过
- 1
- 上传者