2290 問題 Q: 藍(lán)橋杯2018年第九屆真題-采油
時間限制: 1s
內(nèi)存限制: 128MB 提交: 145 解決: 56
題目描述
LQ公司是世界著名的石油公司，為世界供應(yīng)優(yōu)質(zhì)石油。
最近，LQ公司又在森林里發(fā)現(xiàn)了一大片區(qū)域的油田，可以在這個油田中開采n個油井。
LQ公司在這n個油井之間修建了n-1條道路，每條道路連接兩個油井，路徑中間不會路過任何油井，而且這些道路將所有油井連通。
建立油井的時候需要使用一臺大型設(shè)備，運輸起來非常麻煩，LQ公司準(zhǔn)備在其中的一個油井位置建立一個空運站，先將設(shè)備空運到空運站，之后每次經(jīng)過他們建立的道路來運輸這個大型設(shè)備以建立不同的油井，當(dāng)油井建立完畢后再從空運站將大型設(shè)備運走。
為了減少運輸?shù)穆闊?，公司要求大型設(shè)備在道路上運輸?shù)目偮烦淌亲疃痰摹?br />
在建立油井和采油的過程中需要花費一些人力，第i個油井需要花費Bi個人，而一旦油井建成，就需要Si個人一直堅守在油井上進(jìn)行維護(hù)。
當(dāng)然，如果一個人參與了油井的建設(shè)，他可以直接留下來維護(hù)油井，或者參與下一個油井的建設(shè)，但是在維護(hù)油井的人不能再參加后續(xù)油井的建設(shè)了。
現(xiàn)在LQ公司想知道，大型設(shè)備運輸?shù)目偮窂介L度最短是多少？在保證總路徑長度最短的情況下，LQ公司至少需要花費多少人力才能完成所有油井的建立與維護(hù)。
輸入
輸入的第一行包含一個整數(shù)n，表示油井的數(shù)量。油井由1到n依次標(biāo)號。
第二行包含n個整數(shù)，依次表示B1, B2, ?, Bn，相鄰的整數(shù)之間用一個空格分隔。
第三行包含n個整數(shù)，依次表示S1, S2, ?, Sn，相鄰的整數(shù)之間用一個空格分隔。
接下來n-1行描述油井之間的道路，其中的第i行包含兩個整數(shù)a，b，用一個空格分隔，表示一條道路的起點為i+1、終點為a，長度為b，道路是雙向的，設(shè)備可以從任意一端運送到另一端，每條道路都可以經(jīng)過任意多次。數(shù)據(jù)保證任意兩個油井之間都可以通過道路連接。
輸出
輸出包含兩個整數(shù)，用一個空格分隔，表示最優(yōu)情況下大型設(shè)備需要運輸?shù)目偮烦?，以及在總路程最短的情況下最少需要花費的人力數(shù)量。
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點擊這里了解課程詳情