锻炼身体

思路

牛牛希望走的距离尽可能短，牛妹希望牛牛走的距离尽可能长，因此，牛妹会放到一个点 , 该点要满足与牛妹起点 的距离小于该点与牛牛起点的距离，通过 dfs 分别求出 号点和 号点到其他点的距离，对满足条件的点中，取一个与 号点距离的最大值即可。
时间复杂度：

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */

class Solution {
private:
    #define maxn 100010
    vector<int> g[maxn];
    int dis[2][maxn];
public:

    void dfs(int x, int fa, int id) {
        dis[id][x] = dis[id][fa] + 1;
        for (auto v: g[x]) {
            if (v == fa) continue;
            dfs(v, x, id);
        }
    }
    int solve(int n, int x, vector<Point>& Edge) {

        // write code here
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
            dis[0][i] = dis[1][i] = 0;
        }
        for (auto cur: Edge) {
            g[cur.x].push_back(cur.y);
            g[cur.y].push_back(cur.x);
        }
        dfs(1, 0, 0);
        dfs(x, 0, 1);

        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (dis[0][i] > dis[1][i])
                ans = max(ans, dis[0][i]);
        }
        return ans;
    }
};