原題:芮$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$ 裡的所有點中找到編號最大的那個並輸出。
每筆測試資料的第一行輸入兩個正整數 $N、Q$,分別代表節點數量以及查詢數量。
接著輸入 $N−1$ 行,每一行有兩個正整數 $A_i\ , B_i$,代表 $A_i$ 與 $B_i$ 在樹上以一條邊相連。
最後有 $Q$ 行,每行兩個數 $Xi$、$Ki$ 代表查詢內容。
總共輸出 $Q$ 行,第 $i$ 行輸出 $S_i$ 裡的最大編號,也就是對於每個查詢都輸出一行,答案與答案中間需要換行,如果您輸出「我弱,芮$1$奇 $\text{orz}$」,你可以獲得大大的 $\text{WA}$,畢竟芮$1$奇的強是眾所皆知的。
1 2 1 0 1 1
1 1
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
10 3 10 10 8 10 10 10 8 10 10 10 10 10 7
此為範例二的樹:
為了避免實作上的麻煩,芮$1$奇特別把每一行後的空格都刪除了,而且 $N$ 從原本的 $5\times 10^5$ 變成 $10^5$ 了,不用擔心 $\text{stack overflow}$ 的問題了,謝謝芮$1$奇!
------------------------------------------------------------------------------------------------------------------------------------------
$20\%:N,Q\leq 4000$
$80\%:無特別限制$
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|