问题 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

来源

[提交][状态]