zcmimi's blog

arrow_back树形dp共11篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

f_x表示在x放置且x的子树都被覆盖最少多少

g_x表示不在x放置且x的子树都被覆盖最少多少(x可以不被覆盖)

s_x表示在x放置且x的子树都被覆盖最少多少(x一定被覆盖)

f_u = \sum min(f_v,s_v,g_v)

g_u = \sum min(f_v,s_v)

s_u = (\sum \min(f_v,s_v)) - max(0,min(f_v-s_v))

2/2
Search
search