CF1276 D. Tree Elimination
传送门
Solution
考虑树型(dp),设(f_{u,0/1/2/3})分别表示点(u)被自己父亲边之前的边覆盖了,被自己父亲覆盖了,被自己父亲边之后的边覆盖了以及没有覆盖.
那么这个怎么转移?
下面规定小于号就是出现在(v)前面的意思.
考虑一个点的(f_{u,0})的转移:
显然对于选的那个儿子不能在选这条边之前被选(不然就选不了),那么就是(f_{v,2/3}).
这个儿子前面的儿子一定要选,不然这条前面儿子对应的边就不合法.
这个儿子后面的儿子可以选也可以不选,但是不能选父亲,因为父亲已经被匹配了.
综合起来就是:
[f_{u,0}=f_{v,2/3}*prod_{p<v}f_{p,0/1}*prod_{p>v}f_{p,0/2/3}
]
(f_{u,2})的转移类似.
考虑(f_{u,1})的转移,那么有:
对于前面的儿子一定不能选2,3.
对于后面的儿子一定不能选父亲.
综合起来就是:
[f_{u,1}=prod_{son<fa_u}f_{son,0/1}*prod_{son>fa_u}f_{son,0/2/3}
]
(f_{u,3})则等价于前面的都不能选(2/3),所以转移就很明了了.