题目大意是给出一颗树的节点连接关系，只需控制一个一个即可控制与其相邻的节点，问最少需要控制多少节点才能控制整棵树。
很容易抽象出题目的模型是图的最小顶点覆盖问题，对于一般图而言，这一问题是NP问题。但注意到问题的图非常特殊，是树结构，因此很容易想到树形DP。状态转移方程非常简单f[i,0]=∑f[j,1];f[i,1]=1+∑min(f[j,0],f[j,1]);其中f[i,0]表示对于以节点i为根的子树而言，如果不控制节点i，控制整棵子树最少需要控制的节点数；f[i,1]表示对于以节点i为根的子树而言，如果控制节点i，控制整棵子树最少需要控制的节点数。j是i的儿子节点。边界条件为f[k,0]=0;f[k,1]=1，k是叶节点编号。
1646711 2008-09-18 22:35:01 Accepted 1134 FPC 150 440 IwfWcf
博文
toms outlet, http://www.tomsoutlet-stores.com/
回复删除nike roshe, http://www.nikerosherunshoes.co.uk/
prada handbags, http://www.pradahandbagsoutlet.co.uk/
soccer jerseys, http://www.cheapsoccerjersey.net/
michael kors outlet store, http://www.michaelkorsoutlet-store.us.com/
true religion jeans, http://www.truereligionjeansoutlets.us.com/
oakley sunglasses, http://www.oakleysunglasses-outlet.us.com/
nike free 5, http://www.nikefree5.us/
louis vuitton bags, http://www.louisvuittonbag.us.com/
chanel handbags, http://www.chanelhandbags-outlet.co.uk/
chanel handbags, http://www.chanelhandbags-outlet.us.com/
louis vuitton handbags, http://www.louisvuittonhandbag.us/
louis vuitton outlet, http://www.louisvuittonoutlet.in.net/
ghd hair straighteners, http://www.ghdhairstraightenerssale.co.uk/
nba jerseys, http://www.nbajerseys.us.com/
coach outlet, http://www.coachoutletstores.com.co/
true religion jeans, http://www.truereligionjeanscanada.com/
swarovski crystal, http://www.swarovskicrystals.co.uk/
mbt shoes, http://www.mbtshoesoutlet.us.com/
michael kors handbags, http://www.michaelkorshandbags.in.net/
chanel handbags, http://www.chanelhandbagsoutlet.in.net/
michael kors outlet online, http://www.michaelkorsoutletonline.in.net/
polo ralph lauren, http://www.poloralphlauren.us.org/
the north face clearance, http://www.thenorthfaceclearances.us.com/
jordan shoes, http://www.jordan-shoes.us.com/
beats by dr dre, http://www.beatsbydrdre-headphones.us.com/
the north face uk, http://www.thenorthfaces.org.uk/
1003maoqiuyun
zhengjx20160520
回复删除retro jordans 13
jordan 3 powder blue
designer handbags
nike trainers sale
hollister clearance
nike store outlet
coach outlet
cheap jordans
christian louboutin sale
michael kors outlet
kobe 8
michael kors bags
oakley outlet
michael kors handbags
oakley outlet
louis vuitton handbags
retro 11
michael kors outlet
cheap oakley sunglasses
louis vuitton outlet
kd 7 shoes
ray bans
tiffany and co
nfl jerseys
michael kors outlet
jordan retro 8
coach factory outlet online
toms wedges
ray ban sunglasses
michael kors
copy watches
louis vuitton bags
coach outlet store online clearances
cheap ray ban sunglasses
fitflop clearance
michael kors outlet
north face jackets
cheap oakleys
burberry outlet online
michael kors purses
ferragamo outlet
回复删除discount oakley sunglasses
coach outlet online
cheap ray ban sunglasses
snapbacks wholesale
polo ralph lauren
fitflops sale
prada shoes