No testdata at current.
题解：树形DP
定义f[i][j]f[i][j]f[i][j]为以iii为结点的子树中，不放消防栓/放消防栓（j=0/1j=0/1j=0/1）的最小个数
如果在第iii个结点放置消防栓，那么对于结点iii的所有子节点，都可以放置/不放置消防栓
则有f[i][1]=∑min(f[u][0],f[u][1])(u∈i∣u是i的子节点)f[i][1]=\sum_{}^{}min(f[u][0],f[u][1]) (u\in {i|u是i的子节点})f[i][1]=∑min(f[u][0],f[u][1])(u∈i∣u是i的子节点)
如果在第iii个结点不放置消防栓，那么对于结点iii的所有子节点，都必须要放置消防栓
本题属于以下题库，请选择所需题库进行购买
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册
