[NOI2020] 命运

给定一棵 $n$ 个点，以 $1$ 为根的树，现让你对边染色 $(0/1)$ 。有 $m$ 条限制，每条限制形如 $(u_i,v_i)$ ，意为 $u_i$ 到 $v_i$ 的路径上至少要有一条 $1$ 边，其中保证 $u_i$ 是 $v_i$ 的祖先。问染色方案数。
$n,m \le 5 \times 10^5$

$\texttt{Solution}$

以下称 $(u_i,v_i)$ 中 $u_i$ 为限制 $i$ 的上端点，$v_i$ 为其下端点。

考虑 $\texttt{dp}$。令 $dp[x][d]$ 为 $x$ 及 $x$ 的子树已经完成染色，下端点在 $x$ 子树内，上端点不在 $x$ 子树中的，还未被满足的限制中，最深的上端点深度为 $d$ 的染色方案数 。特别地，若没有这样的限制，则方案数存在 $d=0$ 处。

考场并想不到这样的东西，但是有一个非常 $\texttt{naive}$ 的转移：

考虑在 $\texttt{DFS}$ 的过程中，拿每一个 $y \in son(x)$ 来依次更新 $dp[x][d]$。

$$dp[x][d] = \sum_{i=0}^{dep[x]} dp[x][d]\times dp[y][i] + \sum_{i=0}^{d} dp[x][d]\times dp[y][i]+\sum_{i=0}^{d-1} dp[x][i]\times dp[y][d]$$

注意一下原 $\texttt{dp}$ 值不要在中途被覆盖了。

前缀和优化一下，令：

$$sum[x][i] = \sum_{j=0}^{i} dp[x][j]$$

则上面的方程变成：

$$dp[x][d] = dp[x][d] \times (sum[y][dep[x]]+sum[y][d])+dp[y][d]\times sum[x][d-1]$$

首先在每个点上放一棵线段树，点 $x$ 的线段树上第 $i$ 个位置存的是 $dp[x][i]$，然后就可以线段树合并了。

每次线段树合并，首先合并左端点，然后拿两个变量存 $sum[y][dep[x]]+sum[y][d]$ 和 $sum[x][d-1]$，除了 $sum[y][dep[x]]$ 之外，都和下标有关，可以在线段树合并的时候，先合并左端点，然后更新两个值，再去合并右端点。至于 $sum[y][dep[x]]$ ，可以直接先在 $y$ 的线段树上查一下。

初始化的话，发现在没有合并的时候，限制 $(u_i,v_i)$ 只对 $dp[v_i][dep[u_i]]$ 产生 $1$ 的贡献，每次合并之前插进去即可。

复杂度 $O(n\log n)$

标签: 线段树, dp, 线段树合并

添加新评论