「NOI2020」命运

· · 题解

正是因为无法更改，无可违逆，只能接受，命运才会被称之为命运。

题意

给定一颗树，并对树上的边黑白染色，并给出 m 对关系 (u_i,v_i)，保证 u 是 v 的祖先。对于一共 2^{n-1} 种染色方式，计算有多少种染色方式，可以使 m 条 u_i \to v_i 的路径上都至少存在一条黑色的边。答案对 998244353 取模。

题解

看到题意不难想到本题是一个树形 dp。

为了方便表示，我们把「限制关系」简称为「关系」。

而且，我们对于一对关系(u,v)，称 u 为顶部，v 为底部。

一个小发现

我们不难发现，如果一对关系包含了另一对关系，那么我们只需要考虑被包含的关系就可以了，因为反正都要满足，满足小的关系，大的关系自然就满足了。

状态设计

我们设 f_{u,i} 表示只考虑底部在 u 的子树内的限制关系的方案数。

其中 i 表示最深不满足条件的关系的顶部深度为 i，注意，不要忘记这里说的关系全部在 u 的子树里。

自然，i=0 时，f_{u,i} 就表示 u 的子树内的关系全部满足的方案数。

有了状态后，转移就很好做了。考虑更新 f_{u,i}。

可以分讨 u\to v 这条边怎么染色。

\begin{aligned}\sum_{j=0}^{dep_u}f_{v,j}f_{u,i}\end{aligned} \begin{aligned}\sum_{j=0}^{i}f_{v,j}f_{u,i}+\sum_{j=0}^{i-1}f_{v,i}f_{u,j}\end{aligned}

前者表示固定 v 子树的顶部最深的关系的贡献。后者表示固定 u 其他子树的顶部最深的关系的贡献。后者只算到 i-1 是为了防止 f_{u,i}f_{v,i} 算两遍。

我们进行前缀和优化，设 g_{u,i} 表示 \begin{aligned}\sum_{j=0}^{i} f_{u,j}\end{aligned}，所以最终加起来得到转移：

\begin{aligned}f_{u,i}\gets f_{u,i}\times (g_{v,dep_u}+g_{v,i})+g_{u,i-1}\times f_{v,i}\end{aligned}

至此，我们的 \mathcal{O}(n^2) 做法就有了。提交 Link

进一步优化

事实上，我们发现这样的状态设计十分冗余，把深度设计到状态里会发现有很多是无用的，我们只是为了表示出限制关系而已。

当限制关系很少的时候，我们不需要再使用绝对深度，只需要利用限制于限制的相对深度即可。这样优化复杂度就变为了 \mathcal{O(n \min(n,m))}。

正解

观察这个方程：

\begin{aligned}f_{u,i}\gets f_{u,i}\times (g_{v,dep_u}+g_{v,i})+g_{u,i-1}\times f_{v,i}\end{aligned}

我们先对于每个 u 把 f_u 的第二维拍到线段树上。

考虑使用线段树合并优化这个转移。

那么拆开来考虑这个计算;

$g_{v,i}$ 和 $g_{u,i-1}$ 可以动态地维护。我们发现，在合并的时候一定是按照先左后右的顺序去访问到每个叶子节点的。所以这样我们就可以动态去维护前缀和了。 我们开两个变量 $sum_u$、$sum_v$ 动态计算前缀和。具体地，在合并的过程中，访问到就加上。这样去不断计算即可。 最后如果访问到叶子节点 $i$，就代表我们去转移 $f_{u,i}$，直接乘起来即可。 具体说来，我们要维护这样一个线段树： - 单点修改初始值 - 区间和查询 - 合并时的区间乘 这个转换真的很妙妙！ [AC Link](https://www.luogu.com.cn/record/148859082)