可莉又去池塘炸魚啦！琴團長決定親自捉拿可莉將其關禁閉。琴團長不斷地追，可莉不斷地跑。 琴團長和可莉的行動路線可以看做是一個有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)

總結

以上是生活随笔為你收集整理的算法选修(J.琴和可莉)(为选修画上句号)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。