題目描述

隨著考古學者近幾年的研究，逐漸地分析出變態人類文化族群的祖先。同時也知道，每一代人會將其變態基因傳遞給下一代，而下一代的變態指數會比上一代多一。若子代有數個，每個子代帶有的變態性向會有所歧異。

每當新聞報導某個變態父子關係時，人們總會熱議某兩個變態的相似程度。口耳相傳的消息是不可信任的，現在給予事情發生的時間軸，請驗證人們口中的變態相似程度。

變態相似程度定義

$$\textit{sim}(A, B) = \frac{\textit{dist}(\textit{Original}(A), \textit{LCA}(A, B)) \times 2}{\textit{dist}(\textit{Original}(A), A) + \textit{dist}(\textit{Original}(B), B)}$$

其中 $\textit{Original}(A)$ 表示根據事實推測得到的最早源頭祖先，$\textit{dist}(A, B)$ 表示在樹狀圖中兩點的距離，$\textit{LCA}(A, B)$ 表示 $A, \; B$ 最小公共祖先 (Lowest Common Ancestor，簡稱 LCA)。

例如當前知道的祖先關係如下

        P
       / 
      Q
     / \
    A   R
       /
      B
 

• $\textit{Original}(A) = \textit{Original}(B) = P$，
• $\textit{dist}(P, A) = 3, \; \textit{dist}(P, B) = 4, \; \textit{LCA}(A, B) = Q, \; \textit{dist}(Q, P) = 2$。
• 最後 $\textit{sim}(A, B) = \frac{4}{7}$

不幸地，在新聞報導時會因為口誤而傳錯消息，例如在一開始報導 $A$ 的祖先為 $R$，過了不久受到指責才修正回 $A$ 的祖先為 $Q$，錯誤報導的氾濫使得程序檢驗要求有效率且有彈性。不少變態因為錯誤報導而造受批判波及，現在要求你協助檢驗受災程度，好讓那些變態向新聞組織申請賠償。