题解 CF1276D 【Tree Elimination】
xht
2019-12-18 17:51:10
首先,不同的序列数量等同于**消除标记的方案数**。
考虑树形 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;
}
```