NOI 2023 Day 1 C. 深搜

Statement

给定一张 $n$ 个点 $n-1+m$ 条边的简单无向连通图以及其一棵生成树，还有 $k$ 个关键点，求有多少个生成子图存在从某个关键点出发的某一棵 dfs 生成树是给定的生成树，对 $10^9+7$ 取模。

$n,m\leq 5\times 10^5$

TL: 2s

Solution

不难发现如果是判定一个点是否可以以它开始走出这个 dfs 树就是检查是不是没有横叉边。

此时会尝试去想点减边容斥，但很遗憾双不交『子树或子树补』的并之交可以有很多个连通块。

因此只得进行纯粹的子集容斥，钦定非空关键点点集 $S$ 中每个点都可以作为起始点，计算方案并带 $(-1)^{\lvert S\rvert+1}$ 的权。

那你画出来这些有限制点，可以发现如果一个点有三个子树（上方那个子树补也计入）中含有限制点的话，它本身也一定能跑出这个 dfs 树，因为横叉边都被限制掉了。

也就是你先随便定一个点为根，对于每个 $S$ 建出它的虚树，虚树上的点除去虚树根以外都一定进行了限制，虚树根只在其被选中或虚树上度数大于等于 $3$ 时需进行限制（否则应视作两侧关键点直接连起来）。那进一步思考可知这等效于要求多余的边只能在每个虚树边对应的链上或者作为某个没有关键点的子树（上方的子树补需要重新拎起来换根）的前向边。

这些操作都可以摊到 dfn 序上通过线段树进行维护，唯一相对较麻烦的是虚树根未被选中且度数为 $2$ 的情况，那你枚举一侧 dfs 进去把可以选入的边的贡献乘到对应 dfn 区间上即可，然后回溯的时候除回来。那你可以要求枚举到的一侧一定不在重子树，所以复杂度可以分析到 $\mathcal{O}(n\log^2n)$。令人惊讶地是这样直接写暴力无需卡常也能。

然后我就懒得写了，但是口胡下如何做到 $\mathcal{O}(n\log n)$：可以发现刚才提及的一部分中边 $u,v$ 只会挂在 $\operatorname{lca}(u,v)$ 上进行一次贡献，于是你对这些有效端点建出虚树暴力扫就行了，不会写虚树遂摆了。

My Submission.

Update: 其实前面在扯淡，你发现你解决没选定的二度虚树根情况时不需要枚举它一起做，直接离线下来写个换根就是 $\mathcal{O}(n\log n)$ 的，但是我还是懒得重写了。