题解 CF1276D 【Tree Elimination】

xht

2019-12-18 17:51:10

Solution

首先,不同的序列数量等同于**消除标记的方案数**。 考虑树形 dp。我们称一个点被一条边**覆盖**,表示这个点在考虑到这条边时选择消除了这个点上的标记。 设 $f_{x,0/1/2/3}$ 分别表示:点 $x$ 是被自己的父亲边之前的边覆盖的、点 $x$ 是被自己的父亲边覆盖的、点 $x$ 是被自己的父亲边之后的边覆盖的、点 $x$ 没有被覆盖。 那么对于点 $y \in \operatorname{son}_ x$,考虑 $f_ {x,0/2}$: - 点 $y$ 不能被覆盖,即 $f_{y,2/3}$。 - 定义点 $z (\in \operatorname{son}_ x) < y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之前,则点 $z$ 一定要被覆盖,即 $f_ {z,0/1}$。 - 定义点 $z (\in \operatorname{son}_ x) > y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之后,则点 $z$ 可以被覆盖也可以不被覆盖,但不能被边 $(x,z)$ 覆盖,即 $f_ {z,0/2/3}$。 因此有转移: $$ f_ {x, 0/2} = \sum_ {y \in \operatorname{son}_ x} \left( f_ {y, 2 / 3} * \prod_ {z<y} f_ {z, 0 / 1} * \prod_ {z>y} f_ {z, 0 / 2 / 3} \right) $$ 考虑 $f_{x,1}$,有转移: $$ f_{x, 1} = \prod_{y < fa_x} f_{y, 0 / 1} * \prod_{y > fa_x} f_{y, 0 / 2 / 3} $$ 考虑 $f_{x,3}$,有转移: $$ f_{x,3} = \prod_{y} f_{y,0/1} $$ 时间复杂度 $\mathcal O(n)$。 ```cpp const int N = 2e5 + 7; int n, m, k; vi e[N]; modint f[N][4], a[N], b[N], c[N]; void dfs(int x, int fa) { for (int y : e[x]) if (y != fa) dfs(y, x); a[m=k=0] = 1; for (int y : e[x]) if (y == fa) k = m; else ++m, a[m] = a[m-1] * (f[y][0] + f[y][1]), b[m] = f[y][2] + f[y][3], c[m] = f[y][0] + b[m]; c[m+1] = 1; for (int i = m; i; i--) c[i] *= c[i+1]; for (int i = 1; i <= m; i++) f[x][(i>k)<<1] += a[i-1] * b[i] * c[i+1]; f[x][1] = a[k] * c[k+1], f[x][3] = a[m]; } int main() { rd(n); for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x); dfs(1, 0), print(f[1][0] + f[1][2] + f[1][3]); return 0; } ```