b085. 陣列與樹的奇妙物語3 - 第k小區間和 hard version

內容

許多有關於樹的題目經常需要從一條鍊開始想起，為了訓練對於轉換的敏銳度，接下來會有許多從陣列轉換到樹上的經典題目（如果我有空的話）

輸入說明

第一行有一數$N$

接下來有$N$個數自$w_i$為每一個節點的權重。

再來有$N-1$行，每行有兩個數字$a_i, b_i$代表有$a_i$連到$b_i$的無向邊$(1\leq a_i b_i \leq N)$ 保證是樹

最後一行有一個數字$K$代表要求第$K$小路徑

輸出說明

請輸出第$k$小路徑

範例輸入

範例輸出

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 10.0s , <1M
公開測資點#13 (5%): 10.0s , <1M
公開測資點#14 (5%): 10.0s , <1M
公開測資點#15 (5%): 10.0s , <1M
公開測資點#16 (5%): 10.0s , <1M
公開測資點#17 (5%): 10.0s , <1M
公開測資點#18 (5%): 10.0s , <1M
公開測資點#19 (5%): 10.0s , <1M

提示：

$60\%$測資$1\leq N \leq 5000, 1 \leq w_i \leq 10^9$

$40\%$測資$1\leq N \leq 2\times 10^4, 1 \leq w_i \leq 10^9$ (10秒時限）

範例測資同a121

範測的所有區間和由小排到大為
2 3 3 4 6 6 7 9 10 12
因此第6小的是6

標籤:

出處:

[管理者：

william1010121 (郭勝威)

]

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