【OI日記】URAL DP100題 選講
一道比較簡單的樹D，可以當(dāng)作開胃菜。
題目大意
一顆樹，根節(jié)點(diǎn)1的值為1.0，所有葉子節(jié)點(diǎn)的值為0.0，其他節(jié)點(diǎn)值任意。
我們要求所有相鄰兩個(gè)節(jié)點(diǎn)的值差的總和最小。輸出這個(gè)總和。
解題思路
假設(shè)一個(gè)葉子節(jié)點(diǎn)為leaf，他的父節(jié)點(diǎn)為fa，leaf的祖父節(jié)點(diǎn)為g。
由定義得，那么leaf的值為0.0。
那么，此子樹的最優(yōu)結(jié)果為：
由于已經(jīng)知道?。為了使結(jié)果最優(yōu)，應(yīng)當(dāng)滿足條件
。這樣一來，這棵子樹取到最優(yōu)答案
。
推廣一下，如果兒子節(jié)點(diǎn)不是葉子節(jié)點(diǎn)呢？
很簡單，我們掃遍fa的所有子節(jié)點(diǎn)，權(quán)值 ?保證
?就可以了。
更新中。
標(biāo)簽：
