回『基礎題庫』
h900. 超級遞迴測試 - Extreme
標籤 : 重心剖分
通過比率 : 6人/10人 ( 60% ) [非即時]
評分方式：
Tolerant

最近更新 : 2022-05-30 08:40

內容

原題：芮1奇是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時學會了「星爆氣流斬」的招式，而現在要講的，是芮1奇出生後七十一個月二十二天大時，找到家裡地下室，發現世界真相的故事。

芮1奇的國家常常受到巨大猴子騷擾，這隻猴子會把石頭捏碎，當成棒球砸向城牆。這隻猴子身體構造可以看成是一棵樹，且每個節點都有代表的值，士兵們認為這隻巨大猴子的弱點就是以猴子中心的節點 X 當成根，向下 K 代以內，子孫中節點的最大值。但每次士兵打到這個節點時，猴子就只會說：「orzorzorz」，然後就跑走了。

芮1奇在地下室發現猴子真正的弱點不是「中心點 X 向下 K 代以內子孫中的最大值」，而是「與中心點 X 距離 K 以內節點中的最大值」。瞭解到了真相後，芮1奇打算自己去討伐巨大猴子。

芮1奇在碰到巨大猴子之後，突然天搖地動，出現很多想要吃潤餅的巨人，芮1奇知道這些巨人只能幫他撐 10 秒，他得找出與中心點 X 距離 K 以內節點中的最大值。

給你一個 N 個節點的樹 (編號 1∼N)，請你寫個程式支援下列的查詢 Q 次：
查詢內容：第 i 筆查詢給你數對 (Xi ,Ki)，對於與 Xi 距離 Ki 以內的節點 (包含自己) 所形成的點集合 Si，請你從 Si 裡的所有點中找到編號最大的那個並輸出。

輸入說明

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

接著輸入 N−1 行，每一行有兩個正整數 Ai ,Bi，代表 Ai 與 Bi 在樹上以一條邊相連。

最後有 Q 行，每行兩個數 Xi、Ki 代表查詢內容。

  • 1≤N,Q≤105
  • 1≤Ai ,Bi≤N
  • 1≤Xi≤N，0≤Ki≤N
輸出說明

總共輸出 Q 行，第 i 行輸出 Si 裡的最大編號，也就是對於每個查詢都輸出一行，答案與答案中間需要換行，如果您輸出「我弱，芮1奇 orz」，你可以獲得大大的 WA，畢竟芮1奇的強是眾所皆知的。

範例輸入 #1 
1 2
1 0
1 1
範例輸出 #1 
1
1
範例輸入 #2 
10 15
6 4
3 4
2 6
5 2
7 2
10 4
9 10
8 5
1 5
10 2
3 0
9 2
4 9
8 0
2 3
10 3
6 2
1 3
3 2
2 4
10 4
2 5
9 10
7 1
範例輸出 #2 
10
3
10
10
8
10
10
10
8
10
10
10
10
10
7
測資資訊：
記憶體限制： 256 MB
公開 測資點#0 (7%): 2.5s , <1K
公開 測資點#1 (7%): 2.5s , <1M
公開 測資點#2 (7%): 2.5s , <10M
公開 測資點#3 (7%): 2.5s , <10M
公開 測資點#4 (8%): 2.5s , <10M
公開 測資點#5 (8%): 2.5s , <10M
公開 測資點#6 (8%): 2.5s , <10M
公開 測資點#7 (8%): 2.5s , <10M
公開 測資點#8 (8%): 2.5s , <10M
公開 測資點#9 (8%): 2.5s , <10M
公開 測資點#10 (8%): 2.5s , <10M
公開 測資點#11 (8%): 2.5s , <10M
公開 測資點#12 (8%): 2.5s , <10M
提示 ：

此為範例二的樹：

為了避免實作上的麻煩，芮1奇特別把每一行後的空格都刪除了，而且 N 從原本的 5×105 變成 105 了，不用擔心 stack overflow 的問題了，謝謝芮1奇！

------------------------------------------------------------------------------------------------------------------------------------------

20%：N,Q≤4000

80%：無特別限制

標籤:
重心剖分
出處:
[管理者： becaido (Caido) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」