題目 2480:
信息學(xué)奧賽一本通T1575-二叉蘋(píng)果樹(shù)
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 49 解決: 31
題目描述
有一棵二叉蘋(píng)果樹(shù)，如果數(shù)字有分叉，一定是分兩叉，即沒(méi)有只有一個(gè)兒子的節(jié)點(diǎn)。這棵樹(shù)共 N 個(gè)節(jié)點(diǎn)，標(biāo)號(hào) 1 至 N，樹(shù)根編號(hào)一定為 1。
我們用一根樹(shù)枝兩端連接的節(jié)點(diǎn)編號(hào)描述一根樹(shù)枝的位置。一棵有四根樹(shù)枝的蘋(píng)果樹(shù)，因?yàn)闃?shù)枝太多了，需要剪枝。但是一些樹(shù)枝上長(zhǎng)有蘋(píng)果，給定需要保留的樹(shù)枝數(shù)量，求最多能留住多少蘋(píng)果。
我們用一根樹(shù)枝兩端連接的節(jié)點(diǎn)編號(hào)描述一根樹(shù)枝的位置。一棵有四根樹(shù)枝的蘋(píng)果樹(shù)，因?yàn)闃?shù)枝太多了，需要剪枝。但是一些樹(shù)枝上長(zhǎng)有蘋(píng)果，給定需要保留的樹(shù)枝數(shù)量，求最多能留住多少蘋(píng)果。
輸入格式
第一行兩個(gè)數(shù) N 和 Q ，N 表示樹(shù)的節(jié)點(diǎn)數(shù)，Q 表示要保留的樹(shù)枝數(shù)量。
接下來(lái) N?1 行描述樹(shù)枝信息，每行三個(gè)整數(shù)，前兩個(gè)是它連接的節(jié)點(diǎn)的編號(hào)，第三個(gè)數(shù)是這根樹(shù)枝上蘋(píng)果數(shù)量。
接下來(lái) N?1 行描述樹(shù)枝信息，每行三個(gè)整數(shù)，前兩個(gè)是它連接的節(jié)點(diǎn)的編號(hào)，第三個(gè)數(shù)是這根樹(shù)枝上蘋(píng)果數(shù)量。
輸出格式
輸出僅一行，表示最多能留住的蘋(píng)果的數(shù)量。
樣例輸入
5 2 1 3 1 1 4 10 2 3 20 3 5 20
樣例輸出
21
提示
數(shù)據(jù)范圍與提示：
對(duì)于 100% 的數(shù)據(jù)，1≤Q≤N≤100,N≠1，每根樹(shù)枝上蘋(píng)果不超過(guò) 30000 個(gè)。
對(duì)于 100% 的數(shù)據(jù)，1≤Q≤N≤100,N≠1，每根樹(shù)枝上蘋(píng)果不超過(guò) 30000 個(gè)。