題目 2484:
信息學(xué)奧賽一本通T1579-皇宮看守
時間限制: 2s
內(nèi)存限制: 192MB 提交: 70 解決: 29
題目描述
太平王世子事件后，陸小鳳成了皇上特聘的御前一品侍衛(wèi)。
皇宮以午門為起點(diǎn)，直到后宮嬪妃們的寢宮，呈一棵樹的形狀，某些宮殿間可以互相望見。大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個宮殿都要有人全天候看守，在不同的宮殿安排看守所需的費(fèi)用不同。
可是陸小鳳手上的經(jīng)費(fèi)不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。
幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花費(fèi)的經(jīng)費(fèi)最少。
輸入格式
輸入中數(shù)據(jù)描述一棵樹，描述如下：
第一行 n，表示樹中結(jié)點(diǎn)的數(shù)目。
第二行至第 n+1 行，每行描述每個宮殿結(jié)點(diǎn)信息，依次為：該宮殿結(jié)點(diǎn)標(biāo)號 i(0<i≤n)，在該宮殿安置侍衛(wèi)所需的經(jīng)費(fèi) k，該邊的兒子數(shù) m，接下來 m 個數(shù)，分別是這個節(jié)點(diǎn)的 m 個兒子的標(biāo)號r1,r2,?,rm 。
對于一個 n 個結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號在 1 到 n 之間，且標(biāo)號不重復(fù)。
第一行 n，表示樹中結(jié)點(diǎn)的數(shù)目。
第二行至第 n+1 行，每行描述每個宮殿結(jié)點(diǎn)信息，依次為：該宮殿結(jié)點(diǎn)標(biāo)號 i(0<i≤n)，在該宮殿安置侍衛(wèi)所需的經(jīng)費(fèi) k，該邊的兒子數(shù) m，接下來 m 個數(shù)，分別是這個節(jié)點(diǎn)的 m 個兒子的標(biāo)號r1,r2,?,rm 。
對于一個 n 個結(jié)點(diǎn)的樹，結(jié)點(diǎn)標(biāo)號在 1 到 n 之間，且標(biāo)號不重復(fù)。
輸出格式
輸出最少的經(jīng)費(fèi)
樣例輸入
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
樣例輸出
25
提示
樣例解釋：
有六個區(qū)域被安排的情況如左圖所示。
如右圖，灰色點(diǎn)安排了警衛(wèi)，2 號警衛(wèi)可以觀察 1,2,5,6，3 號警衛(wèi)可以觀察 1,3，4 號警衛(wèi)可以觀察 1,4。
總費(fèi)用：16+5+4=25
有六個區(qū)域被安排的情況如左圖所示。
如右圖，灰色點(diǎn)安排了警衛(wèi)，2 號警衛(wèi)可以觀察 1,2,5,6，3 號警衛(wèi)可以觀察 1,3，4 號警衛(wèi)可以觀察 1,4。
總費(fèi)用：16+5+4=25
數(shù)據(jù)范圍與提示：
對于 100% 的數(shù)據(jù)，0<n≤1500。