原題：芮$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$ 代表查詢內容。
- $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$
總共輸出 $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
公開 測資點#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\times 10^5$ 變成 $10^5$ 了，不用擔心 $\text{stack overflow}$ 的問題了，謝謝芮$1$奇！
------------------------------------------------------------------------------------------------------------------------------------------
$20\%：N,Q\leq 4000$
$80\%：無特別限制$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||