广义串并联图とP6790 [SNOI2020] 生成树

广义串并联图と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。对于重边的判断，我们再加边时就要把重边合并掉，保证图中时时刻刻没有重边。