锻炼身体

思路

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

相关推荐

如题,八股刚开始学,准备好好沉淀八股,但是害怕没实习经历,简历筛选过不去,现在找实习却感觉都是已读不回,接下来该怎么安排呢?求教
Java抽象带篮子:具体背什么八股我都帮你整理好了,可以去看看我的八股专栏,这个比较详细,如果你觉得内容有点多记忆负担比较大的话,我还在更新最常问八股整理贴,是不是很贴心?
点赞 评论 收藏
分享
11-06 10:58
已编辑
门头沟学院 嵌入式工程师
双非25想找富婆不想打工:哦,这该死的伦敦腔,我敢打赌,你简直是个天才,如果我有offer的话,我一定用offer狠狠的打在你的脸上
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务