今天有一棵樹上面有$N$個節點(編號$1 \sim N$)，而且編號為$1$的點是根節點，接著請您寫個程式支援下列的查詢$Q$次：
查詢內容：第$i$筆查詢給你數對$(X_i,K_i)$，對於節點$X_i$的所有$K_i$代以內的子孫與自己所形成的點集合$S_i$，請您從$S_i$裡的所有點中找到編號最大的那個並輸出。
每筆測試資料的第一行輸入兩個正整數$N$、$Q$，分別代表節點數量以及查詢數量。
接著有一行$ N - 1$個數，其中第$i$個的數字代表編號$ i + 1$的父節點編號$F_{i+1}$，注意編號$1$的點是根節點，因此沒有父節點、不輸入$F_1$。
最後有$Q$行，每行兩個數$X_i$、$K_i$代表查詢內容。
總共輸出$Q$行、第$i$行輸出$S_i$裡的最大編號，也就是對於每個查詢都輸出一行，答案與答案中間需要換行，如果您輸出「我弱，我什麼都不會」，您可以獲得大大的$\text{WA}$，畢竟裝弱是不好的行為。
8 5 1 5 2 1 2 3 3 1 1 2 2 3 0 1 3 1 2
5 6 3 8 6
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 2.0s , <10M
公開 測資點#4 (10%): 2.0s , <10M
公開 測資點#5 (10%): 3.0s , <10M
公開 測資點#6 (10%): 3.0s , <10M
公開 測資點#7 (10%): 3.0s , <10M
公開 測資點#8 (10%): 3.0s , <10M
公開 測資點#9 (10%): 3.0s , <10M
範例說明：以下是範例測試1畫出來的樣子
其中紅色區域是第一個查詢，$S_1 = ( 1, 2, 5 )$，也就是點$1$的自己與$1$代以內子孫，$max ( S_1 ) = 5$，所以答案為$5$。
藍色區域則是第二個查詢，$S_2 = ( 2, 4, 6 )$，也就是點$2$的自己與$2$代以內子孫，所以答案為$6$，注意這個$case$點$2$其實並沒有第$2$代的子孫，所以$S_2$是它自己以及第$1$代子孫所形成之集合。
綠色的則是第三個查詢，$S_3 = ( 3 )$，也就是點$3$的自己與$0$代以內子孫，所以答案為$3$，注意這個$case$的$K_i = 0$，所以$S_3$裡只有它自己。
註：由於生測資的時候沒有出現意外，因此每一行數字的最後都沒有空格。另外這題不建議使用Python作答，由於輸入量頗大，C++建議使用ios_base::sync_with_stdio(false);、Java使用BufferedReader/Writer。在解題之前請注意C++/Java在ZeroJudge遞迴$2 \times 10^5$就會吃$ \color{blue}{RE}$，但這題有$ N = 5 \times 10^5 $，那您怎麼辦呢?
對於所有測試資料滿足:
$1 ≤ N, Q ≤ 5 \times 10^5$
$1 ≤ F_i, X_i ≤ N$
$0 ≤ K_i ≤ N - 1$
(註:$K_i = 0$就是指只有自己一點的狀況)
子題配分:
$Subtask\ 1\ (30\%)$ : $N, Q ≤ 700$
$Subtask\ 2\ (20\%)$ : $N ≤ 1000, Q ≤ 5 \times 10^5$
$Subtask\ 3\ (50\%)$ : 同原題限制
※2022/05/16 18:08更，由於出現了非期望出現的解，於是加強測資並且rejudge。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||