d767.
血緣關係
內容
給一張祖譜,詢問 A , B 兩人關係最近的共同祖先 以及 A , B 之間的親等
example 1
親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。
※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。
example 1
親等計算 : 往上算到與要計算的人共同祖先處，再往下算到那個人，數多少就是幾親等。
※ 輸入的人的編號，必為 1~N ，而兒女編號必大於父母本身的編號。
輸入說明
第一行兩個數字 N , Q
分別代表接下來會有 N 行數字分別代表該人的兒女編號(以 0 表結束)，
再來會有 Q 行
每行上會有兩個數字 A , B ，代表要求出 A , B 兩人的關係最近的共同祖先
以及 A , B 之間的親等。
詳細請參考Sample Input。
(N≦3,0000, 1≦A,B≦N, Q≦N2)
輸出說明
輸出兩個數字最近的共同祖先 以及 A , B 之間的親等
範例輸入
#1
7 6 2 3 0 4 5 0 6 7 0 0 0 0 0 4 5 4 2 4 4 4 3 1 7 2 3
範例輸出
#1
2 2 2 1 4 0 1 3 1 2 1 2
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (94%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1M
公開 測資點#3 (1%): 1.0s , <1M
公開 測資點#4 (1%): 3.0s , <10M
公開 測資點#5 (1%): 3.0s , <10M
公開 測資點#6 (1%): 1.0s , <10M
公開 測資點#0 (94%): 1.0s , <1K
公開 測資點#1 (1%): 1.0s , <1K
公開 測資點#2 (1%): 1.0s , <1M
公開 測資點#3 (1%): 1.0s , <1M
公開 測資點#4 (1%): 3.0s , <10M
公開 測資點#5 (1%): 3.0s , <10M
公開 測資點#6 (1%): 1.0s , <10M
提示 ：
※ 在此未符合實際事實，暫定一個人的兒女不超過6個
Ranged Minimum/Maximum Query(RMQ)
Least Common Ancestors (LCA)
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||