i201: 超級遞迴測試
Tags : 優化 資料結構 遞迴
Accepted rate : 3人/8人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-16 18:08

Content

今天有一棵樹上面有$N$個節點(編號$1 \sim N$),而且編號為$1$的點是根節點,接著請您寫個程式支援下列的查詢$Q$次:

查詢內容:第$i$筆查詢給你數對$(X_i,K_i)$,對於節點$X_i$的所有$K_i$代以內的子孫與自己所形成的點集合$S_i$,請您從$S_i$裡的所有點中找到編號最大的那個並輸出。

Input

每筆測試資料的第一行輸入兩個正整數$N$、$Q$,分別代表節點數量以及查詢數量。

接著有一行$ N - 1$個數,其中第$i$個的數字代表編號$ i + 1$的父節點編號$F_{i+1}$,注意編號$1$的點是根節點,因此沒有父節點、不輸入$F_1$。

最後有$Q$行,每行兩個數$X_i$、$K_i$代表查詢內容。

Output

總共輸出$Q$行、第$i$行輸出$S_i$裡的最大編號,也就是對於每個查詢都輸出一行,答案與答案中間需要換行,如果您輸出「我弱,我什麼都不會」,您可以獲得大大的$\text{WA}$,畢竟裝弱是不好的行為。

Sample Input #1
8 5
1 5 2 1 2 3 3
1 1
2 2
3 0
1 3
1 2
Sample Output #1
5
6
3
8
6
測資資訊:
記憶體限制: 512 MB
公開 測資點#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
Hint :

範例說明:以下是範例測試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。

Tags:
優化 資料結構 遞迴
出處:
Chi's Coding Problem [管理者:
Ststone1687 (使用C++的都邪教)
]


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