https://ac.nowcoder.com/acm/contest/6915/B
题意
疫情期间,牛牛整天摊在床上沉溺于手机,身体日渐虚胖,因此牛妹拿走家中的 wifi 路由器,迫使牛牛下床来拿到路由器。在这过程中,牛牛想要在尽可能短的时间内拿到路由器,而牛妹却希望牛牛多走一会儿。现假设牛妹家中有 nnn 个房间,任意两个房间有且仅有一条路径,起初路由器在编号为 xxx 的房间内,牛牛在编号为 1 的房间内,牛牛与牛妹速度相同,当俩人同时开始移动,牛牛要经过几个房间才能拿到路由器。
只要牛牛和路由器处在同一房间,便看作牛牛已拿到路由器。
输出
牛牛最多需要经过的房间数(包括 1 号房间在内)。
示例1
5,2,[(1,2),(2,3),(3,4),(2,5)]
输出
4
说明
当牛妹将路由器放到 4 号房间时,牛牛需要经过 1 -> 2 -> 3 -> 4 共四个房间。
-
可以发现如果一个节点
u
到点1
的距离( )小于等于到点
X
的距离( )则点u
一定不是
最优点,反之是最优点V
-
我们先以
1
为根节点dfs
求得每个节点的深度dep1[i]
则
dep1[i]
代表点i
到点1
的距离 -
再以
X
为根节点dfs
求得么个节点的深度depX[i]
则
depX[i]
代表点i
到点x
的距离 -
#ifdef debug
struct Point {int x;int y;
};
#endifint dep1[MAXN]; //从 1 号点为根dfs出所有深度
int depX[MAXN]; //从 X 号点为根dfs出所有深度vector<int> G[MAXN];class Solution {public:/*** 牛牛经过的房间数。* @param n int整型 * @param x int整型 * @param Edge Point类vector * @return int整型*/void dfs(int u, int fa, int level, int* dep) {dep[u] = level;for(auto v : G[u])if(v != fa) dfs(v, u, level+1, dep);}int solve(int n, int x, vector<Point>& edge) {for(int i=0; i<=n; i++) G[i].clear();for(auto p : edge)G[p.x].push_back(p.y), G[p.y].push_back(p.x);dfs(1, 1, 1, dep1); //计算以 1 为根的所有深度dfs(x, x, 1, depX); //计算以 X 为根的所有深度int ans = 0;for(int i=1; i<=n; i++)if(dep1[i] > depX[i])ans = max(ans, dep1[i]);return ans;}
};