题解 | #寻找牛妹#

一.题目描述
NC571寻找牛妹
n个结点之间有n-1条边，有一个目标数组X，其中有m个目标结点，从根结点走到每个目标结点Xi，每条边最多可以走两次，问从根结点走到每一个目标节点最多可以经过几条边?
二.算法(暴力搜索)

首先我们要理解题意，但对于n个节点之间有n-1条边我们可以认为其是一个树，由于其连通性我们可以做出如下分析：
，下面我们利用暴力搜索来解决，下面给出完整代码：

class Solution {
public:
    int num[200005];//记录孩子个数(并不是一层而是下方全部)
    int dis[200005];//记录距离
    vector<int>mp[200005];
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        for(int i=0;i<n-1;i++){
            //记录双向边
            mp[u[i]].push_back(v[i]);
            mp[v[i]].push_back(u[i]);
        }
        vector<int>cn(m);
        int ans=2*(u.size()-1);
        dfs(1,0,0);
        for(int i=0;i<m;i++){
            //利用前面推导公式计算
            cn[i]=ans-dis[x[i]]-2*(num[x[i]]-1);
        }
        return cn;
    }
    int dfs(int now,int pre,int cn){
        //now表示当前搜索结点,pre表示前一次搜索的节点，cn表示当前结点到根结点的距离
        dis[now]=cn;
        int sum=0;
        for(auto &j:mp[now]){
            if(j!=pre){
                sum+=dfs(j,now,cn+1)+1;
            }
        }
        num[now]=sum;
        return sum;
    }
};

时间复杂度： 对于每一个节点只有一次访问
空间复杂度： 利用了二维vector来存图
优缺点：代码实现简单，但是利用的公式推导难理解
三.算法(java实现)
可以利用java的ArrayList来代替c++的vector来实现，思路相同，下面是完整代码：

import java.util.*;
public class Solution {
    ArrayList<Integer>[]mp;
    int[]dis;
    int[]num;
    public int[] solve (int n, int m, int[] u, int[] v, int[] x) {
        //对数组和ArrList分配空间
        mp=new ArrayList[n+1];
        dis=new int[n+1];
        num=new int[n+1];
        int[]cn=new int[m];
        for(int i=1;i<=n;i++){
            mp[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            //双向边
            mp[u[i]].add(v[i]);
            mp[v[i]].add(u[i]);
        }
        dfs(1,0,0);

        int sum=2*(u.length-1);
        for(int i=0;i<m;i++){
            //利用推导公式
            cn[i]=sum-dis[x[i]]-(num[x[i]]-1)*2;
        }
        return cn;
    }
    int dfs(int now,int pre,int cn){
        //now表示当前搜索结点,pre表示前一次搜索的节点，cn表示当前结点到根结点的距离
        dis[now]=cn;
        int cnt=0;
        for(int j:mp[now]){
            if(j!=pre){
                cnt+=dfs(j,now,cn+1)+1;
            }

        }
        num[now]=cnt;
        return cnt;
    }
}

时间复杂度： 对于每一个节点只有一次访问
空间复杂度： 利用了ArrayList二维来存图
优缺点：代码实现简单，但是利用的公式推导难理解