Toggle navigation
Reach-Top OJ
问题
题解
知识点/来源
学习
视频
状态
信息技术
排名
微信答题
初赛练习
挑战赛
随机挑战赛
挑战赛
竞赛/作业
Login
问题 5285 --虎哥玩游戏
5285: 虎哥玩游戏
★★★★★
时间限制:
5 Sec
内存限制:
128 MB
提交:
27
解决:
10
[
提交
][
状态
][命题人:
]
题目描述
今天虎哥与朋友又在一起玩游戏,游戏在一个树状的地图上进行,树的每条边上可进行双向移动,1号顶点为树根。
虎哥从顶点1出发,朋友从顶点x(x≠1)出发,虎哥让朋友先移动。在每次移动中,可以停留在当前顶点或移动到相邻顶点。
当虎哥走到他朋友所在的顶点时,游戏结束。虎哥希望移动总步数尽量少,而朋友希望移动总步数尽量大。
现在请帮忙计算一下这个游戏会移动多少步?
输入
第一行包含两个整数n与x(2≤n≤2e5, 2≤x≤n).
接下来的n-1行,每行有两个整数a,b(1≤a,b≤n),表示树的一条边。输入确保输入的所有边会构成一棵树。
输出
输出虎哥与朋友在游戏中总共的移动步数。
样例输入
Copy
4 3 1 2 2 3 2 4
样例输出
Copy
4
提示
样例2:
输入:
5 2
1 2
2 3
3 4
2 5
输出:
6
样例1的树如图所示:
红色顶点为虎哥的开始位置;蓝色位置为朋友的开始位置,他希望从顶点3出发移动尽可能多的步数。他们移动过程如下(A表示虎哥,B表示朋友):
B: 停留在顶点3
A: 移动到顶点2
B: 停留在顶点3
A: 移动到顶点3,游戏结束。
样例2的树如图所示:
移动过程如下(A表示虎哥,B表示朋友):
B: 移动到顶点3
A: 移动到顶点2
B: 移动到顶点4
A: 移动到顶点3
B: 停留在顶点4
A: 移动到顶点4
来源
ZJX2022+天梯赛#33F
[
提交
][
状态
]