題目 2092:
藍(lán)橋杯算法訓(xùn)練VIP-Castles
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 66 解決: 0
題目描述
戰(zhàn)爭在世界歷史中扮演了重要角色。與現(xiàn)代戰(zhàn)爭不同，中世紀(jì)的軍隊(duì)主要忙于奪取和控制貴族的私有設(shè)防住宅——城堡。一個(gè)進(jìn)攻軍隊(duì)的規(guī)模是軍隊(duì)奪取和控制這些建筑杰作的能力的重要影響因素。
奪取城堡會(huì)使用最少需要的士兵數(shù)量。一些士兵在進(jìn)攻中會(huì)死去。奪取城堡后，一些士兵被要求留在城堡里防衛(wèi)其他軍隊(duì)的進(jìn)攻。當(dāng)然，留守的士兵數(shù)量根據(jù)不同的城堡而不同。軍隊(duì)指揮官有義務(wù)來考慮進(jìn)攻成功需要的士兵數(shù)量。例如，圖中有5個(gè)城堡，右下角的城堡需要至少20個(gè)士兵才能進(jìn)攻成功，沒有人在進(jìn)攻中會(huì)死去，軍隊(duì)前進(jìn)后10個(gè)士兵必須留在城堡里。
你需要確定一個(gè)軍隊(duì)奪取和控制一個(gè)特定地區(qū)的所有城堡所需要的最小規(guī)模。出于安全因素，該地區(qū)的任意一對城堡之間有且僅有一條路徑。移動(dòng)到相鄰的未奪取城堡就會(huì)發(fā)動(dòng)對該城堡的進(jìn)攻。任何城堡都可以作為第一個(gè)被進(jìn)攻的城堡，不用管軍隊(duì)是怎么到那里的。一旦某個(gè)城堡被奪取，要求的士兵數(shù)量被留在城堡里保衛(wèi)它，若還有未奪取城堡，則軍隊(duì)剩余的人繼續(xù)前進(jìn)奪取其他城堡。軍隊(duì)可以安全到達(dá)已被奪取的城堡的相鄰城堡。但由于被進(jìn)攻的潛在可能，軍隊(duì)在同一方向上經(jīng)過同一條路最多一次。
奪取城堡會(huì)使用最少需要的士兵數(shù)量。一些士兵在進(jìn)攻中會(huì)死去。奪取城堡后，一些士兵被要求留在城堡里防衛(wèi)其他軍隊(duì)的進(jìn)攻。當(dāng)然，留守的士兵數(shù)量根據(jù)不同的城堡而不同。軍隊(duì)指揮官有義務(wù)來考慮進(jìn)攻成功需要的士兵數(shù)量。例如，圖中有5個(gè)城堡，右下角的城堡需要至少20個(gè)士兵才能進(jìn)攻成功，沒有人在進(jìn)攻中會(huì)死去，軍隊(duì)前進(jìn)后10個(gè)士兵必須留在城堡里。
你需要確定一個(gè)軍隊(duì)奪取和控制一個(gè)特定地區(qū)的所有城堡所需要的最小規(guī)模。出于安全因素，該地區(qū)的任意一對城堡之間有且僅有一條路徑。移動(dòng)到相鄰的未奪取城堡就會(huì)發(fā)動(dòng)對該城堡的進(jìn)攻。任何城堡都可以作為第一個(gè)被進(jìn)攻的城堡，不用管軍隊(duì)是怎么到那里的。一旦某個(gè)城堡被奪取，要求的士兵數(shù)量被留在城堡里保衛(wèi)它，若還有未奪取城堡，則軍隊(duì)剩余的人繼續(xù)前進(jìn)奪取其他城堡。軍隊(duì)可以安全到達(dá)已被奪取的城堡的相鄰城堡。但由于被進(jìn)攻的潛在可能，軍隊(duì)在同一方向上經(jīng)過同一條路最多一次。
輸入格式
第一行包含一個(gè)整數(shù)n，表示該地區(qū)的城堡數(shù)。
接下來n行每行包含三個(gè)整數(shù)a_i, m_i和g_i，表示成功奪取城堡i需要的最少士兵數(shù)量，在進(jìn)攻中會(huì)死去的士兵數(shù)量和必須留守的士兵數(shù)量。
接下來n行每行包含三個(gè)整數(shù)a_i, m_i和g_i，表示成功奪取城堡i需要的最少士兵數(shù)量，在進(jìn)攻中會(huì)死去的士兵數(shù)量和必須留守的士兵數(shù)量。
接下來n - 1行每行包含兩個(gè)整數(shù)x_i和y_i，表示一條直接連接城堡x_i和城堡y_i的道路。
對于30%的數(shù)據(jù)，1 <= n <= 10。
對于100%的數(shù)據(jù)，1 <= n <= 100，1 <= a_i <= 1000，0 <= m_i <= a_i，1 <= g_i <= 1000。
輸出格式
一行包含一個(gè)整數(shù)，表示奪取和控制該地區(qū)的所有城堡所需要的最少士兵數(shù)量。
樣例輸入
3 5 5 5 10 5 5 5 1 1 1 3 2 3
樣例輸出
22
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情