锻炼身体

思路

牛牛希望走的距离尽可能短,牛妹希望牛牛走的距离尽可能长,因此,牛妹会放到一个点 , 该点要满足与牛妹起点 的距离小于该点与牛牛起点的距离,通过 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;
    }
};
全部评论

相关推荐

喜欢走神的孤勇者练习时长两年半:池是池,发是发,我曾池,我现黑
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务