题目的主要信息：

n个房间一共n-1个通道相连，每个房间可互相到达，这就是一棵无向树
牛牛一开始在1号房间，要到另一个房间去找牛妹，这个过程中每条痛道最多只能走两次，且如果当前牛牛有没走过的通道可以走，牛牛就不会去走走过一次的通道
每次走过一条通道花费1金币，一共m个查询，每次查询牛妹在 $x_{i}$ 号房间，问最少要携带多少金币才能保证任何情况都能找到牛妹**（即每次查询的时候先走通往不了的牛妹房间的分支，最后走通往牛妹的房间的分支，这种情况都能满足，那任意情况都可以满足）**
题目的意思是每次查询都从1号房间开始

方法一：两次dfs

具体做法： 上面已经提到了，我们至少要满足任何情况都可以找到牛妹，就需要找到每次试错都是通往不是牛妹房间的分支，最后再回来再通往牛妹房间的分支的情况。图片说明图示无疑是最坏的情况，如果这个情况都能够满足，那么其他情况也可以。我们再来看最后的路线结果，可以分成三个部分：

黄色部分属于别的分支的，都经过了两次，绿色部分属于目标节点后续子树部分的，没有经过，紫色部分属于从1号节点到目标节点的深度，只经过了一次。黄色部分难以计算，由此，我们可以用这个树总边数（ $n - 1$ )的2倍，减去绿色部分边的2倍和紫色部分边的和。其中紫色部分，属于根节点到目标节点的深度，绿色部分边数等于目标节点子树的节点数，我们可以dfs遍历整棵树，求得每个节点所处的深度depth，同时根据深度我们还能得到从根节点到目标节点最短路径上的目标节点的前序节点。利用这个前序节点，我们可以dfs遍历以目标节点为根的子树（因为不访问前序节点，那我们只会访问绿色部分），遍历这棵子树我们就可以得到子树的节点数，减去根这个就是子树的边数subnode。最后用公式 $2 * (n - 1) - d e p t h - 2 * s u b n o d e$ 直接计算即可。

class Solution {
public:
    //dfs计算深度和每个深度的前序节点
    void dfs1(vector<vector<int>>& G, vector<pair<int, int>>& depth, int k, int cur, int pre){
        for(int i = 0; i < G[cur].size(); i++){
            if(G[cur][i] != pre) //不能是前序节点
                dfs1(G, depth, k + 1, G[cur][i], cur); //子节点深度+1
        }
        depth[cur].first= k; //记录深度
        depth[cur].second = pre; //记录该节点的前序
    }
    //根据该节点和前序节点，遍历这棵子树，求所有的子节点数
    void dfs2(vector<vector<int>>& G, int cur, int pre, int& subnode){
        subnode++;
        for(int i = 0; i < G[cur].size(); i++){
            if(G[cur][i] != pre) //不能是前序节点
                dfs2(G, G[cur][i], cur, subnode);
        }
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<int> res(m);
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < u.size(); i++){ //构建图
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        vector<pair<int, int> > depth(n + 1); //记录每个节点的深度
        dfs1(G, depth, 0, 1, 0); //dfs统计每个节点所处的深度
        for(int i = 0; i < m; i++){ 
            int subnode = -1; //根节点不算数要先减掉
            dfs2(G, x[i], depth[x[i]].second, subnode); //计算以目标节点为根的子树有多少节点
            res[i] = 2 * (n - 1) - depth[x[i]].first - 2 * subnode; //对于每个查询，公式计算
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n m)$ ，构建图复杂度为 $O (n)$ ，dfs每个节点访问一次，复杂度为 $O (n)$ ，最后一共 $m$ 次查询，每次查询都有一个dfs，取最大次幂就是 $O (n m)$
空间复杂度： $O (n)$ ，二维数组的大小不会超过边数

方法二：一次dfs

具体做法： 同样的类似方法一，我们要找到每个结点的depth和subnode，但是我们可以在第一次dfs遍历的时候，利用递归自底向上相加的方式得到每个节点的子树大小，只需要一个数组来记录每个节点的子树大小即可，这样查询的时候直接使用数组不需要再dfs一次了。

class Solution {
public:
    int dfs(vector<vector<int>>& G, vector<int>& subnode, vector<int>& depth, int k, int cur, int pre){
        int count = 0;
        for(int i = 0; i < G[cur].size(); i++){
            if(G[cur][i] != pre) //不能是前序节点
                count += dfs(G, subnode, depth, k + 1, G[cur][i], cur); //子节点深度+1
        }
        subnode[cur] = count;  //子节点数
        depth[cur] = k; //深度
        return count + 1;
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x) {
        vector<int> res(m);
        vector<vector<int> > G(n + 1);
        for(int i = 0; i < u.size(); i++){ //构建图
            G[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
        }
        vector<int> subnode(n + 1, 0); //记录每个节点的子节点数
        vector<int> depth(n + 1, 0); //记录每个节点的深度
        dfs(G, subnode, depth, 0, 1, 0); //dfs统计子节点数和每个节点所处的深度
        for(int i = 0; i < m; i++) //对于每个查询，公式计算
            res[i] = 2 * (n - 1) - depth[x[i]] - 2 * subnode[x[i]];
        return res;
    }
};

复杂度分析：

时间复杂度： $O (m + n)$ ，构建图复杂度为 $O (n)$ ，dfs每个节点访问一次，复杂度为 $O (n)$ ，最后一共 $m$ 次查询
空间复杂度： $O (n)$ ，二维数组的大小不会超过边数

题解 | #寻找牛妹#

题目的主要信息：

方法一：两次dfs

方法二：一次dfs