1 条题解

  • 0
    @ 2025-2-18 20:03:57
    #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
    上传者