[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, 线段树合并

添加新评论