ob75sess 2021-10-14 18:09 采纳率: 100%
浏览 816
已结题

算法与数据结构实验题 6.1 小明的果树

算法与数据结构实验题 6.1 小明的果树

★实验任务

小明种了一棵果树,这棵树有 n 个节点,树根为 1 号节点,现在这颗果树上有 m 个节 点长出果实(根节点 1 有可能长出果实),小明要从节点 1 出发采集这些果实,从一个节点爬 到相邻的另一个节点所需要的时间为 1,采集果实不需要时间,问小明如果要采集这 m 个果 实,从节点 1 出发,并且最后需要回到节点 1,最少需要多少的时间。

★数据输入

第 1 行输入两个数字 n 和 m 第 2 行到第 n 行每行输入两个数字 a 和 b 表示节点 a 和节点 b 之间有一条边 第 n+1 行输入 m 个数字,第 i 个数字 v[i]表示在 v[i]号节点上长有果实 n<=100000 0<m<=n

★数据输出

对于每个输入,输出一个数字,表示最少需要花费的时间。
输入:
4 2
1 2
1 3
2 4
2 3
输出:
4

  • 写回答

1条回答 默认 最新

  • CSDN专家-sinJack 2021-10-14 18:12
    关注
    #include <iostream>  
    #include <vector>    
    #define maxn 100005  
    using namespace std;    
    vector<int> E[maxn], dp(maxn), v(maxn);    
    int dfs(int u, int fa) {    
        int bo = (v[u] ? 1 : 0);    
        for(int i = 0; i < (int)E[u].size(); i++) {  
            int  t = E[u][i];
            if(t != fa) {
                 if(dfs(t, u)) {  
                    bo = 1;  
                    dp[u] += dp[t] + 2;  
                }
            }    
        }   
        return bo;    
    }    
    int main(void) {    
        int n, m, s, t, k;  
        cin >> n >> m;  
        for(int i = 0; i < n - 1; i++) {  
            cin >> s >> t;  
            if(s > t) swap(s, t);
            E[s].push_back(t);    
            E[t].push_back(s);
        }   
        for(int i = 0; i < m; i++) {  
            cin >> k, v[k] = 1;  
        }  
        dfs(1, -1);
        cout << dp[1] << endl;    
        return 0;    
    }    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

    报告相同问题?

    问题事件

    • 系统已结题 10月25日
    • 已采纳回答 10月17日
    • 创建了问题 10月14日

    悬赏问题

    • ¥65 页面调接口时加载卡住不响应
    • ¥35 用C语言解决编程问题
    • ¥15 unity硬件连接与使用
    • ¥15 鱼缸加热棒的数据分析或者实际案例也行
    • ¥15 postgresql11安装完成后,pgadmin无法启动
    • ¥15 (标签-无人机|关键词-Matlab代码)
    • ¥15 执行shell脚本提示参数太多
    • ¥15 困扰好久了,电脑的串口调试助手向单片机发送一个字符(如:字符‘1’到‘8’),单片机点亮对应的灯(如发送字符‘2’则点亮第2个灯)并给电脑回复信息:已点亮第x个灯(其中 x 要替换成对应的数字)
    • ¥15 求减少这个c++程序内存的解决方案
    • ¥30 改正代码,错误比较多