题解 P3351 【[ZJOI2016]电阻网络】

jerry3128 · 2021-07-14 21:41:19 · 题解

【[ZJOI2016]电阻网络】

题目大意：

• 给定一张 n 个点 m 条边的无向图，问有多少种选择端点的方法，使得这张图是扩展二端串并联图。
• n,m \leq 10^{5}

题解：

• 前置知识：二端串并联图 与 SPQ Tree
• 如何判定一个二端串并联图：
  • 我们考虑选择的源点和汇点，如果两个点在同一点双以内，则我们可以在 SPQ 上直接判定两点是否在同一串联节点以内可以得到。
  • 否则从割点分离每个点双，判断两个点双路径上的每个点双的两个端点是否为二端串并联图。
  • 此时容易发现 不在路径上的点 的形态发现不论怎么妖魔鬼怪都与此时的电阻无关。
• 考虑对每个点双建出 SPQ 树，同时计算出该点双内部的对答案的贡献，即每个 串联节点 的儿子中任意选两个 非源汇 的方案数。
• 同时这个点双的根仍然可能是其他点双的根或者一部分。
• 令一个数组 dp 记录每个节点 作为源点并且作为点双根 的时候能够向上贡献二端串并联图的个数。这样在上面他作为点双一部分时就可以直接调用贡献算出跨越点双的答案。
• 在串联节点和并联节点分别加减该有的贡献就可以直接算出答案。

代码私信。