TopCoder

User's AC Ratio

0.0% (0/5)

Submission's AC Ratio

0.0% (0/84)

Tags

Description

黑色騎士團的聯繫方式是用飛鴿傳書,每個團員都有隻快慢不相等的鴿子。(當然是階級越高的人擁有的鴿子飛的越快)

現在團長要發布一個命令給全部團員知道,便派出了他的神速鴿來傳信(可以在一瞬間到任何地方的超強鴿子)。
而黑色騎士團的階級分布是樹狀的,代表每個團員都只有一個直屬的長官(團長除外),而每個團員也只會聽他直屬長官的話。
因此,每位長官在接到命令時,都會寫信給自己的直屬部下,就這樣一傳十,十傳百,最後讓所有團員都知道這個命令。

照理來說,團員在接到命令時,應該也要派出自己的鴿子幫忙傳訊息,但是由於命令不是由他發的,為了愛惜自己的鴿子就會要求神速鴿幫忙送信,所以神速鴿總是會帶著一堆信飛來飛去。

每個團員看信的時間都不一樣,而每當神速鴿送信過來後,他們除了看自己長官的信外,還會無聊的把其他信也都看完,然後再寫信給他的部下,這段時間內神速鴿都會一直待在這團員那。(設一個團員看每封信的時間都一樣,而且因為是用抄的,所以寫信的時間會跟看一封信的時間一樣)。
也因為這樣,雖然神速鴿飛很快,但都必須等到團員看完信才能飛到下一個地方,所以總會花很久的時間神速鴿才會回到團長身邊。為了能讓神速鴿早點歸來,團長希望你幫牠規劃路線,且告訴團長最少要多久神速鴿才會回來。

P.S.回來的定義是,最後一個團員把神速鴿放走。

Input Format

每一組測資第一行會有兩個數字n(1≦n≦1000000)和V,n代表有多少個團員(編號為1~n),V代表團長的編號(1≦V≦n)。
接下來有n個數字Ci(0<Ci≦1000000),代表每個團員看一封信的時間。
接下來有n-1行,每含有兩個數字xi和yi,代表xi和yi有直屬關係,但不確定誰是誰的部下。

Output Format

請輸出最少要花多久的時間神速鴿才會回到團長那邊。

Sample Input 1

5 1
3 1 1 3 2
1 2
1 3
4 3
3 5

Sample Output 1

24

Hints

第一組範例測資的說明:

神速鴿最優路線:3號團員(看信1+寫信1)->4號團員(看信3*2+寫信3)->5號團員(看信2*3+寫信2)->2號團員(看信1*4+寫信1)
1+1+6+3+6+2+4+1=24

Scoring:

對於 40% 的測試資料,n≦1000 。

Problem Source

原TIOJ1568 / Problem Setter: poloo5582
(Adapted From: Beijing 2004)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 18000 65536 262144 1
1 18000 65536 262144 2
2 18000 65536 262144 3
3 18000 65536 262144 4
4 18000 65536 262144 5
5 18000 65536 262144 6
6 18000 65536 262144 7
7 18000 65536 262144 8
8 18000 65536 262144 9
9 18000 65536 262144 10