h900. 超級遞迴測試 - Extreme
Tags : 重心剖分
Accepted rate : 5人/8人 ( 62% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

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

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

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

Input

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

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

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

  • $1 \leq N, Q \leq 10^5$
  • $1 \leq A_i\ , B_i \leq N$
  • $1 \leq X_i \leq N,0 \leq K_i \leq N$
Output

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

Sample Input #1
1 2
1 0
1 1
Sample Output #1
1
1
Sample Input #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
Sample Output #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
Hint :

此為範例二的樹:

為了避免實作上的麻煩,芮$1$奇特別把每一行後的空格都刪除了,而且 $N$ 從原本的 $5\times 10^5$ 變成 $10^5$ 了,不用擔心 $\text{stack overflow}$ 的問題了,謝謝芮$1$奇!

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

$20\%:N,Q\leq 4000$

$80\%:無特別限制$

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

Status Forum 排行

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