d767: 血緣關係
Tags : LCA RMQ
Accepted rate : 135人/151人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-04 19:08

Content
給一張祖譜,詢問 A , B 兩人關係最近的共同祖先 以及 A , B 之間的親等
example 1

親等計算 : 往上算到與要計算的人共同祖先處,再往下算到那個人,數多少就是幾親等。

※ 輸入的人的編號,必為 1~N ,而兒女編號必大於父母本身的編號。
Input

第一行兩個數字 N , Q
分別代表接下來會有 N 行數字分別代表該人的兒女編號(以 0 表結束),
再來會有 Q 行
每行上會有兩個數字 A , B ,代表要求出 A , B 兩人的關係最近的共同祖先
以及 A , B 之間的親等。
詳細請參考Sample Input
(N≦3,0000,    1≦A,B≦N,     Q≦N2)

Output
輸出兩個數字最近的共同祖先 以及 A , B 之間的親等
Sample Input #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
Sample Output #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
Hint :

※ 在此未符合實際事實,暫定一個人的兒女不超過6個

Ranged Minimum/Maximum Query(RMQ)
Least Common Ancestors (LCA)

Tags:
LCA RMQ
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」