创世纪

题目描述 给你一个 \(n\) 个点 \(n\) 条边的有向图，若选了当前节点，那么当前节点的儿子节点至少有一个不能选。求最多能选多少个点。 具体思路 显然是一棵基环树，因此考虑基环树 dp。 我们先不管环的条件，先考虑朴素的树形 dp。 设 \(f_{x,0}\) 表示 \(x\) 节点不选，最多 ......

# [创世纪](https://www.acwing.com/problem/content/description/361/) 首先考虑树的情况。 为了方便，还是将基环树的边反向。 令 $f[u][0/1]$ 表示当前点不选/选的答案。 1. 若当前的点不选，那么其子节点任意，$\sum\max( ......