算法选修(J.琴和可莉)(为选修画上句号)

可莉又去池塘炸鱼啦！琴团长决定亲自捉拿可莉将其关禁闭。琴团长不断地追，可莉不断地跑。 琴团长和可莉的行动路线可以看做是一个有n个节点的无根树，初始时琴团长在A点，可莉在B点，她们互相知道对方的位置。 琴团长想尽快抓到可莉，可莉不想让琴团长快速抓到自己，两人都采用最优的策略。 每个回合轮流操作，每次操作可以选择留在原地或者移动到相邻的节点，由可莉开始第一个回合。 现在请你计算一下，多少个回合后琴团长可以抓到可莉？

Input

有多组测试样例 第一行包含三个整数 n,A,B( 1 ≤ A,B ≤ n ≤ 2 × 10^5) 接下来 n - 1行包含两个整数 u,v 表示 u,v 之间有一条边

Output

对于每一个测试样例 共一行, 输出一个整数表示答案

Sample Input

4 1 3 1 2 2 3 2 4 5 1 2 1 2 2 3 3 4 2 5

Sample Output

2 3

 

这篇就不粘代码了,说一下思路,之前粘代码被称为“机院福利姬”,虽然没有查重,但是对那些真正自己写代码的人不是很友好,我的思路是，因为是个无根树，用spfa或者是dijkstra找到这两个点到每一个点的距离，然后遍历n个点，如果逃跑的人，到某个点的距离小于追的人，那么记录这个值，然后这个值的最大值就是结果 ,很好理解,注意多组输入,(虽然题里没说),然后说一句题外话,我不是大佬,埋土大佬很多,我就是个菜鸡,因为最近写算法选修的原因,很多人关注我,很多大佬是不想写,让我钻了空子(明年还有选修,我接着写hh)