POJ 3659 Cell Phone Network

需要考虑和节点\(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)) \]

POJ 3659 Cell Phone Network

上一篇:html下拉菜单


下一篇:简单详细讲解js闭包