题解 | #寻找牛妹#

题目关键信息：
n个结点之间有n-1条边，有一个目标结点数组，其中有m个目标结点，从根结点走到每个目标结点，每次可以经过最多多少条边，其中，每条边最多可以走两次
方法一：dfs
每条边最多可以走两次，因此,从根结点到目标结点的通道只能走一次，目标结点和它的所有孩子结点的通道都不用走，因此，从根结点到目标结点经过的最多边数=allPath-从根结点到目标结点的距离-目标结点的所有孩子数*2

• 因此，可以定义一个数组存储每个结点到根结点的距离，用数组存储每个结点的孩子数，用一个二维数组list来保存每个结点以及它的相邻结点，相当于一个无向图
• 填充数组和数组：采用dfs，从根结点开始递归搜索孩子结点，递归终止条件是遇到叶子结点，返回0，每次都将当前结点的孩子结点数量累加，最后递归得到结点的所有孩子结点数量，每个结点到根结点的距离随着递归深度增加而增加，因此用len记录深度

Java版本

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param u int整型一维数组 
     * @param v int整型一维数组 
     * @param x int整型一维数组 
     * @return int整型一维数组
     */
    ArrayList<Integer>[]list;
    int[]dist;
    int[]child;
    public int[] solve (int n, int m, int[] u, int[] v, int[] x) {
        // write code here
        list=new ArrayList[n+1];
        dist=new int[n+1];//保存根结点到其他结点的距离
        child=new int[n+1];//每个结点的孩子数
        for(int i=1;i<=n;i++){
            list[i]=new ArrayList<>();
        }
        for(int i=0;i<n-1;i++){
            list[u[i]].add(v[i]);//无向图
            list[v[i]].add(u[i]);
        }
        dfs(1,0,0);//从第一个结点开始搜索，第一个结点的父结点初始化为0
        int[]res=new int[m];
        int allpath=2*u.length;//每条通道都走两次的数量
        for(int i=0;i<m;i++){
            res[i]=allpath-dist[x[i]]-child[x[i]]*2;//根结点到目标结点的通道只能走一次，目标结点到它所有的孩子结点的通道不用走
        }
        return res;
    }
    //curr:当前结点,pre:当前结点的父节点，len:当前结点到根结点的距离
    int dfs(int curr,int pre,int len){
        dist[curr]=len;
        int cnt=0;
        for(int c:list[curr]){
            if(c==pre)continue;//为了不重复计算通道，如果当前结点的孩子结点与它的父结点相同，直接跳过
            cnt+=dfs(c,curr,len+1)+1;//计算当前结点的孩子数，同时结点到目标结点的距离随着递归深度增加而增加
        }child[curr]=cnt;//记录每个结点的孩子数
        return cnt;
    }
}

复杂度：
时间复杂度：,只有一重循环并且dfs每个结点至少访问一次，时间复杂度为
空间复杂度：递归栈的大小不超过n,二维数组list的大小不超过,因此空间复杂度为

方法二：dfs+bfs
根结点到目标结点经过的最多边数公式为;与方法一不同的是，方法二我们采用广度优先搜索计算每个结点到根结点的距离，同时增加一个visit数组记录结点是否被访问过，因为我们在存储结点的时候是把它们当做无向图存储，所以在计算结点的孩子数和结点到根结点的距离时可能会重复访问某个结点，因此visit数组默认初始化为false，每次访问过后该结点处更改为true，下次就不会再访问该结点
用bfs计算结点到根结点的距离时，需要利用辅助队列q，先让根结点入队，访问每一个层的结点，因为每层结点到根结点的距离是相等的，因此len不变，继续下一层结点入队，直到当前层的所有结点访问完后，

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param x int整型vector 
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {

        // write code here
        vector<vector<int>>list(n+1);//每个结点数组里包含孩子数组
        vector<int>dist(n+1);//记录每个结点到根结点的距离
        vector<int>child(n+1);//记录每个结点的所有孩子数
        vector<bool>visit(n+1,false);//记录结点是否被访问
        for(int i=0;i<n-1;i++){
            list[u[i]].push_back(v[i]);
            list[v[i]].push_back(u[i]);
        }
        dfs(1,list,visit,child);
        for(int i=0;i<n+1;i++)visit[i]=false;//visit需要重新初始化
        bfs(1,list,dist,visit);
        vector<int>res(m);
        int allpath=2*u.size();//每条通道都走两次的数量
        for(int i=0;i<m;i++){
            res[i]=allpath-dist[x[i]]-child[x[i]]*2;//根结点到目标结点的通道只能走一次，目标结点到它所有的孩子结点的通道不用走
        }
        return res;
    }
    void bfs(int curr,vector<vector<int>>&list,vector<int>&dist,vector<bool>&visit){
        int len=0;//len:当前结点到根结点的距离
        queue<int>q;
        q.push(curr);//先将1入队
        while(!q.empty()){
            int size=q.size();
            while(size--){//每一层结点到根结点的距离相等，因此每次一层结点一起计算
                int node=q.front();
                q.pop();
                if(visit[node])continue;//已经访问过的结点直接跳过，避免同一条通道计算两次
                visit[node]=true;
                dist[node]=len;//同一层的结点距离相等
                for(int c:list[node])//将结点的孩子入队
                    q.push(c);
            }
            len++;//下一层结点距离加一
        }
    }
    int dfs(int curr,vector<vector<int>>&list,vector<bool>&visit,vector<int>&child){
        visit[1]=true;
        int cnt=0;
        for(int c:list[curr]){
            if(!visit[c]){
                visit[c]=true;//避免重复计算同一条通道
                cnt+=dfs(c,list,visit,child)+1;//当前结点孩子数累加得到结点的所有孩子数
            }
        }child[curr]=cnt;//记录每个结点的孩子数
        return cnt;//递归终止条件是到达叶子结点，返回孩子数为0
    }
};

复杂度：
时间复杂度：dfs和bfs中，每个结点都至少访问一次，solve函数循环只有一重，因次时间复杂度为
空间复杂度：辅助队列和递归栈的大小不超过n，list二维数组的大小不超过,因次空间复杂度最差为