题目简述

给定一个仙人掌图（每个点最多属于一个简单环），求随机选择一个点集 $S$，其生成的斯坦纳树（Steiner Tree）边数的期望值。 由于总方案数是 $2^n$，我们需要计算所有可能的点集 $S$ 对应的斯坦纳树边数之和，最后除以 $2^n$（模意义下乘逆元）。

核心思路：边的贡献 + 环的处理

根据期望的线性性，总期望等于每条边在斯坦纳树中出现的概率之和。 也就是说，我们不需要枚举集合 $S$，而是计算每条边被“选中”的次数。

对于图中的边，分为两种情况：树边（桥） 和 环上的边。

1. 树边（桥）的处理

如果一条边 $(u, v)$ 是桥，去掉它会将图分成两个连通块，大小分别为 $x$ 和 $n-x$。 这条边被选入斯坦纳树，当且仅当：点集 $S$ 在这两个连通块中都至少选了一个点。

• 连通块 1 选点的方案数：$2^x - 1$（排除全不选）。
• 连通块 2 选点的方案数：$2^{n-x} - 1$。
• 贡献：$(2^x - 1)(2^{n-x} - 1)$。

这一步在代码的 dfs1 末尾处理。

2. 环的处理

对于环上的边，不能简单地判断断开后的连通性。仙人掌图的性质允许我们单独处理每个环。 对于一个长度为 $t$ 的环，假设环上挂着的子树大小分别为 $b_1, b_2, \dots, b_t$。 如果在环上（包括挂着的子树）选择了一些点，这些点在环上的分布将决定使用了多少环上的边。

结论：在环上，斯坦纳树的边数 = 环长 $t$ - 环上被选点分割出的最大间隙（Max Gap）。

• 如果没有选点，边数为 0。
• 如果选了点，这些点把环分成了若干段“空白边”，其中最长的一段空白边不会被包含在斯坦纳树中，其余边都会被包含。

因此，我们需要计算所有选点方案下 $(t - \text{Max Gap})$ 的总和。

代码详解

变量定义

• ans：累加的总答案（所有方案的边数之和）。
• pw2[]：$2$ 的幂次预处理。
• e[]：邻接表存图。
• siz[]：DFS 序中的子树大小。
• a[]：当前找到的环上的节点列表。
• b[]：环上节点 $a[i]$ 挂着的子树大小（不包含环上其他部分）。

函数解析

1. dfs1(u, fa)：找环与处理树边 这是主 DFS 函数。

• 它计算子树大小 siz。
• 判环：如果遇到 v 已经被访问过且 v != fa，说明找到了一个环（v 是环的“根”）。
  • 利用 far 数组（记录父节点）回溯，将环上的点存入 a[]。
  • 调用 dfs2 计算挂在环上每个点的子树大小，存入 b[]。
  • 调用 sol() 处理这个环的贡献。
• 处理树边：如果 !u[tag]（当前边不在环上），则按照树边的公式计算贡献：

  int x = u[siz];
  int y = n - u[siz];
  ans = (ans + (lnt)(pw2[x] - 1) * (pw2[y] - 1)) % M;
  

2. sol()：环上的 DP 这是最复杂的部分，用于计算环的贡献。 问题转化为：在一个圆环上，每个点 $i$ 有 $2^{b[i]}-1$ 种被选中的权重（如果不选该点子树内的点，则视为该点未被选中）。求所有方案的 $(t - \text{Max Gap})$ 之和。

• 枚举起点 $s$：为了打破环的对称性，强制规定环上的点 $s$ 是第一个被选中的点（即 $s$ 被选中，且 $s$ 之前的若干点构成回绕的 Gap）。
• DP 状态： f[i][j] 表示：
  • 当前考虑到环上的第 $i$ 个点（相对于起点 $s$）。
  • 点 $i$ 被选中（其子树内有选点）。
  • 从起点 $s$ 到点 $i$ 这段链上，相邻选中点之间的最大间隙是 $j$。
• 转移： 我们需要枚举上一个选中点 $k$ ($s \le k < i$)。 新产生的间隙是 $i - k$。 新的最大间隙是 $\max(\text{旧间隙}, i-k)$。 为了优化复杂度，代码中使用 g[j] 数组维护了前缀和/辅助转移。
• 计算贡献： 当确定起点是 $s$，终点是 $i$ 时，链上的最大间隙是 $j$。 此时还有一个回绕间隙（从 $i$ 绕回 $s$），长度为 $t - (i - s)$。 整个环的最大间隙为 $\max(j, t - (i - s))$。 贡献累加：

  ans = (ans + (lnt)(t - max(t + s - i, j)) * f[i][j]) % M;
  

  这里 t - max(...) 就是该方案下斯坦纳树在环上的边数。

3. dfs2 简单的辅助函数，用于在发现环之后，重新遍历环上节点挂着的子树，计算 b[i]（即不通过环上边能到达的节点数量）。

复杂度分析

• $N \le 200$。
• 树边处理是 $O(N)$。
• 环处理 DP：
  • 外层枚举起点 $s$：$O(t)$。
  • 内层 DP 状态 $i, j$：$O(t^2)$。
  • 总计 $O(t^3)$。
• 由于 $\sum t = N$，最坏情况下也就是一个大环 $O(N^3)$。
• 对于 $N=200$，运算量在 $10^6 \sim 10^7$ 级别，非常轻松通过。

总结

代码通过 Tarjan 类似的思路找环（利用 DFS 树的返祖边），将仙人掌图拆解为树边和简单环。树边直接用组合数学计算，简单环则通过枚举起点的区间 DP（$O(N^3)$）来统计斯坦纳树的边数贡献。最后乘上 $2^{-n}$ 得到期望。