黑色騎士團的聯繫方式是用飛鴿傳書,每個團員都有隻快慢不相等的鴿子。(當然是階級越高的人擁有的鴿子飛的越快)
現在團長要發布一個命令給全部團員知道,便派出了他的神速鴿來傳信(可以在一瞬間到任何地方的超強鴿子)。
而黑色騎士團的階級分布是樹狀的,代表每個團員都只有一個直屬的長官(團長除外),而每個團員也只會聽他直屬長官的話。
因此,每位長官在接到命令時,都會寫信給自己的直屬部下,就這樣一傳十,十傳百,最後讓所有團員都知道這個命令。
照理來說,團員在接到命令時,應該也要派出自己的鴿子幫忙傳訊息,但是由於命令不是由他發的,為了愛惜自己的鴿子就會要求神速鴿幫忙送信,所以神速鴿總是會帶著一堆信飛來飛去。
每個團員看信的時間都不一樣,而每當神速鴿送信過來後,他們除了看自己長官的信外,還會無聊的把其他信也都看完,然後再寫信給他的部下,這段時間內神速鴿都會一直待在這團員那。(設一個團員看每封信的時間都一樣,而且因為是用抄的,所以寫信的時間會跟看一封信的時間一樣)。
也因為這樣,雖然神速鴿飛很快,但都必須等到團員看完信才能飛到下一個地方,所以總會花很久的時間神速鴿才會回到團長身邊。為了能讓神速鴿早點歸來,團長希望你幫牠規劃路線,且告訴團長最少要多久神速鴿才會回來。
P.S.回來的定義是,最後一個團員把神速鴿放走。
每一組測資第一行會有兩個數字n(1≦n≦1000000)和V,n代表有多少個團員(編號為1~n),V代表團長的編號(1≦V≦n)。
接下來有n個數字Ci(0<Ci≦1000000),代表每個團員看一封信的時間。
接下來有n-1行,每含有兩個數字xi和yi,代表xi和yi有直屬關係,但不確定誰是誰的部下。
請輸出最少要花多久的時間神速鴿才會回到團長那邊。
第一組範例測資的說明:
神速鴿最優路線:3號團員(看信1+寫信1)->4號團員(看信3*2+寫信3)->5號團員(看信2*3+寫信2)->2號團員(看信1*4+寫信1)
1+1+6+3+6+2+4+1=24
原TIOJ1568 / Problem Setter: poloo5582
(Adapted From: Beijing 2004)
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 |