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

Question

算法与数据结构实验题 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

Answer 1

#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;    
}