TopCoder

tmwilliamlin
我的中文很爛

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

19.8% (33/167)

Tags

Description

盩僰麌好不容易突破了防線,正想繼續施展自己的電力時,忽然發現自己腳下的土地逐漸隆起,定睛一看,原來包括自己所站的地方,共有$N$個高於地表的地形。
正當盩僰麌以為又是之前那群人的時候,面前出現了一個熟悉的面孔。沒錯,正是弢哥,那個自稱從不裝弱的弢哥。

「為什麼你就不能像我一樣從不裝弱呢!」弢哥憤慨地說,原來,這一切都是弢哥設下的圈套,他早就知道盩僰麌裝弱成性、積習難改,原本以為他能在自己的潛移默化下,改掉裝弱的壞習慣,沒想到他卻變本加厲,甚至影響他人,使得到處都瀰漫著裝弱的氛圍。事情惡化到這種地步,弢哥只好使用這個迷宮將盩僰麌困住,讓他不再到處傳播裝弱的不良風氣。

所謂迷宮,就是由盩僰麌現在所在的隆起所組成的。若將這些地形由左至右編號為$1~N$的話,盩僰麌所在的位置正好為編號$s$的地形。第$i$個地形會向左連接$L_i$條天橋、向右連接$R_i$條天橋(天橋只能單向通行),天橋的組成看似毫無章法,卻隱藏弢哥的巧思。每個地形其實都暗中裝置了一個可以降低裝弱指數的機器,第$i$個地形上的可以降低$a_i$點裝弱指數,而天橋的穩固程度則是連接的兩個地形上機器威力的xor值(也就是若天橋連接$(i,j)$兩地形,則其穩固程度為$a_i\oplus a_j$)。弢哥當然希望迷宮的堅固程度最大,因此對於第$i$個地形,他會從左邊的地形中選擇$L_i$個與$i$連接起來穩固程度最高的地形做相連,右邊亦然。

當然,上述所提及的機關(包括會降低裝弱指數的機器、橋相連背後的意義等)都沒有讓盩僰麌知道,因此盩僰麌很放心地透過天橋四處走動。一臺機器會在當盩僰麌通過它所在的地形時降低盩僰麌$a_i$點的裝弱指數,為了節能減碳愛地球,發動過後的機器從此不再運作。弢哥想要知道,在最好的情況下,也就是每一種可能的走法中,盩僰麌的裝弱指數最多會降低多少。

Input Format

輸入第一行包含兩個正整數$N, s$,代表地形的數量以及盩僰麌一開始的位置。
接著一行包含$N$個整數$a_i$,代表第$i$個地形上的機器威力。
接著$N$行每行有兩個整數$L_i,R_i$,代表從第$i$個地形向左、向右連的天橋數量。

對於所有測資,$N\leq 5\times 10^ 5, 0\leq a_i \leq 10^ 6, 1\leq s \leq N, 0\leq L_i \leq i - 1, 0\leq R_i \leq N - i,\sum{L_i} + \sum{R_i} \leq 10^ 6$,保證所有$a_i$皆相異。

子任務(測資)額外限制分數
1(0~7)$N\leq 5000$10
2(8~13)$R_i = 0$20
3(14~17)$0\leq L_i \leq 1, 0\leq R_i \leq 1$19
4(0~28)無限制51

Output Format

輸出一個整數代表最好的狀況下,盩僰麌的裝弱指數會降低多少。

Sample Input 1

5 4
1 4 2 5 0
0 1
1 0
1 0
1 1
1 0

Sample Output 1

12

Hints

Problem Source

Problem Set by waynetuinfor

Subtasks

No. Testdata Range Score
1 0~7 10
2 8~13 20
3 14~17 19
4 0~31 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 1048576 262144 1 4
1 2500 1048576 262144 1 4
2 2500 1048576 262144 1 4
3 2500 1048576 262144 1 4
4 2500 1048576 262144 1 4
5 2500 1048576 262144 1 4
6 2500 1048576 262144 1 4
7 2500 1048576 262144 1 4
8 2500 1048576 262144 2 4
9 2500 1048576 262144 2 4
10 2500 1048576 262144 2 4
11 2500 1048576 262144 2 4
12 2500 1048576 262144 2 4
13 2500 1048576 262144 2 4
14 2500 1048576 262144 3 4
15 2500 1048576 262144 3 4
16 2500 1048576 262144 3 4
17 2500 1048576 262144 3 4
18 2500 1048576 262144 4
19 2500 1048576 262144 4
20 2500 1048576 262144 4
21 2500 1048576 262144 4
22 2500 1048576 262144 4
23 2500 1048576 262144 4
24 2500 1048576 262144 4
25 2500 1048576 262144 4
26 2500 1048576 262144 4
27 2500 1048576 262144 4
28 2500 1048576 262144 4
29 2500 1048576 262144 4
30 2500 1048576 262144 4
31 2500 1048576 262144 4