需要考虑和节点\(u\)相邻的节点的选择情况,所以既要看儿子,也要看父亲。选择\(u\),选择\(u\)的儿子,选择\(u\)的父亲都对子树答案有影响。
对节点\(u\)来说,\(u\)被支配的情况有三种:选择\(u\)自身,选择\(u\)的父亲,选择\(u\)的儿子,三种情况选择其一即可使得\(u\)被支配。
状态表示:
\(f(u,0)\):不选\(u\),选择\(u\)的父亲。
\(f(u,1)\):选\(u\)。
\(f(u,2)\):不选\(u\),选择\(u\)的儿子。
状态转移:
若不选\(u\),选择\(u\)的父亲,则\(u\)的儿子要么选择自己来支配自身,要么选择自己的子节点来支配自身。
\[f(u,0)=\sum_{j \in Son(u)} \min(f(j,1),f(j,2))
\]
若选\(u\),则\(u\)的子节点可选可不选,其中不选的情况又分为:1.选择子节点支配自身。2.选择父节点支配自身。
\[f(u,1)=1+\sum_{j \in Son(u)} \min(f(j,1),f(j,0),f(j,2))
\]
若不选\(u\),选择\(u\)的儿子,则\(u\)至少需要选择某一个儿子支配,其余儿子可选可不选。
枚举每个子节点\(j\)支配\(u\)的
\[f(u,2)=\min(f(u,2),f(k,1)+\sum_{j \in Son(u)且j\ne k} \min(f(j,1),f(j,2)))
\\=\min(f(u,2),f(u,0)-\min(f(k,1),f(k,2))+f(k,1))
\]