广义串并联图とP6790 [SNOI2020] 生成树
前置知识:广义串并联图
定义广义串并联图为不存在与 \(K_4\)(即 \(4\) 个点的完全图)同胚的子图的连通无向图(同胚是指可以通过边的放缩而互相转化的图,即 \((x\leftrightarrow y\leftrightarrow z)\Leftrightarrow (x\leftrightarrow z)\) )。也即不存在四个点使得这个点之间有 \(6\) 条边不交的路径。
广义串并联图有性质:可以通过删除一度点、缩二度点、去除重边使原图变为一个点。这样我们在缩图过程中,每条边相当于原图的一个子图,我们可以在边上维护子图的信息,然后合并。
本题
图 \(G\) 是一个广义串并联图。证明:因为仙人掌对于任意四个点只有最多四条不交路径,多一条边后也最多五条,无法达到 \(K_4\) 的六条,故得证。
考虑对于每条边 \((u,v)\) 代表的子图,维护 \(f(u,v)\) 表示子图使得 \((u,v)\) 联通的方案数,即生成树数量。维护 \(g(u,v)\) 表示子图使得 \((u,v)\) 不连通的方案数,即子图分成两个生成树,\(u,v\) 各属于其中一个。接下来是合并信息。
- 删除一度点时,对于一度点 \(u\) 和唯一连边 \((u,v)\),\((u,v)\) 一定要连通,所以直接计入答案 \(ans\gets ans\times f(u,v)\)。
- 缩二度点时,对于二度点 \(u\),和连边 \((u,x),(u,y)\)。要使 \((x,y)\) 联通,则 \((u,x),(u,y)\) 都要连通,即 \(f(x,y)=f(u,x)\times f(u,y)\)。要使 \((x,y)\) 不连通,则有一个不连通,且 \(u\) 要连通,所以 \(g(x,y)=f(u,x)\times g(u,y)+g(u,x)\times f(u,y)\)。
- 去除重边时,对于两条边 \((u,v)',(u,v)''\),若 \(u,v\) 连通,则两条边有且只有一个连通,即 \(f(u,v)=f(u,v)'\times g(u,v)''+g(u,v)'\times f(u,v)''\)。若 \(u,v\) 不连通,则两条边都不连通,\(g(u,v)=g(u,v)'\times g(u,v)''\)。
实现时可以用 map
存一个点的连边,写一个 check(x)
函数,检查一个点是否是一度点或二度点,再递归 check
。对于重边的判断,我们再加边时就要把重边合并掉,保证图中时时刻刻没有重边。