#LAISIR26. 神諭傳送網
神諭傳送網
🧮 題目名稱:神諭傳送網
📝 題目背景:
在遠古文明中,神殿之間透過一套神祕的傳送網進行資訊的傳遞。
每個神殿在接收到神諭後,會立刻轉交給它所控制的第一個下屬神殿,而其他下屬神殿的訊息會透過「前一位」下屬再轉交。
每個神殿只記錄:
- 接收到神諭後,要傳給的那一個第一個下屬。
- 每個下屬還會記錄它之後還要轉交給哪個下屬神殿。
也就是說,每個神殿的下屬實際形成了一條鏈狀傳遞路線。而每個下屬,又可以自己展開新的下屬傳遞網。
🎯 任務
給定神殿的轉送規則,請你回答:
對於某個神殿,它一旦收到神諭,最終會有多少個不同的神殿接收到這份神諭(不含自己),並且這份神諭會被轉送至最深的幾層(自己為第 1 層)。
📥 輸入格式:
第一行一個整數 n
(1 ≤ n ≤ 10⁵),表示神殿總數。
接下來 n
行,每行格式如下:
name first
name
表示神殿名稱。first
是此神殿收到神諭後,第一個要通知的下屬名稱。若無,則為"null"
。
再接下來 n
行,每行格式如下:
a b
- 表示神殿
a
的傳遞對象是b
(它的後續下屬)。 - 若
a
沒有後續,則b = "null"
。
最後一行是一個字串 root
,代表神諭從哪個神殿開始傳送。
📤 輸出格式:
兩個整數,以空格分隔:
- 接收到神諭的神殿總數(不含起始點);
- 神諭能傳遞到的最深層數(包含起始點為第 1 層)。
📘 輸入範例:
6
A B
B C
C null
D E
E F
F null
B C
C null
E F
F null
E null
A
📤 輸出範例:
3 4
Related
In following homework: