锻炼身体

思路

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

相关推荐

hso_:哈哈哈哈哈哈我没offer一样在同一道题开喷了
投递深圳同为数码等公司10个岗位
点赞 评论 收藏
分享
12-02 17:22
已编辑
西安交通大学 Java
华为 昇腾 ai软件开发 薪资20k x (14-16),职级13A,5%公积金,c/cpp
BLOOMING7:闭眼滴滴,华子给的又少又累
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务