自动搬运

查看原文

来自洛谷，原作者为

	Orange_qwq 废物

搬运于2025-08-24 21:56:47，当前版本为作者最后更新于2023-01-17 23:52:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

这里是题目。

主体代码没问题，高精度愣是搞了好久。。。

思路

这题我们首先要判断图是不是仙人掌，然后要求出把仙人掌进行删边之后得到的图仍然是连通图的方案数。

先看看这个方案数怎么求。

对于一个仙人掌图进行删边操作，显然我们只能删环上的边。对于每一个环，我们可以选择任意一条边删掉，也可以选择不删。设第 $i$ 个环的边数为 $num_i$，我们可以这样计算得到答案 $ans$：

然后问题就变成了怎么求环和 $num_i$。

我们可以用 $\text{dfs}$，构造出图的生成树。在 $\text{dfs}$ 的过程中，我们可以记录下每个节点 $x$ 的初始访问时间 $dfn_x$ 和能够往上最大程度追溯到的节点 $low_x$。如果走了返租边（访问到了访问过的节点），那么说明出现了环。

那环的边数呢？我们构造出来生成树，如果有返租边，那么一定是先一直向下访问、构造，然后到了某个节点 $a$ 就突然往上到了另一个节点 $b$。由于我们一直向下构造，再加上一条边回到 $b$，出现了一个环，所以这个环的边数就是我们从 $b$ 一直向下走到 $a$ 走的边数加上这条返租边。这个边数我们可以用深度的差得到，设第 $i$ 个节点的深度为 $dep_i$，则环的边数为 $dep_b - dep_a + 1$。

剩下的问题是怎么判断图是不是仙人掌了。由图观察可知，如果 某个节点的子孙的返租边到了这个节点之上 与 这个节点发出的返租边 的和 $\ge 2$，那么就说明这个节点在两个环里了，该图不是仙人掌。

您可能要问为啥不用 $\text{bfs}$，因为这个菜鸡认为 $\text{bfs}$ 有点难搞，并且比较擅长 $\text{dfs}$。 $\text{dfs}$ 可以构造出生成树，比较好处理点或边出现的顺序关系（例如可以处理深度，利用 $dfn$ 和 $low$ 处理环），所以选择用 $\text{dfs}$。

代码

注意最后的答案可能是一个很大很大的数。

我们要用高精度存答案。

可能要用压位高精，因为这个菜鸡 MLE 了好多发，最后把 $base$ 改成 $1e14$ 才过的。

void dfs(int x, int fa) {
	++num;
	int cnt = 0;                         // 求该节点所在环的个数 
	dfn[x] = low[x] = ++tot;
	for (int i = he[x]; i; i = ne[i]) {
		int y = e[i];
		if (y == fa) continue; 
		if (!dfn[y]) {                   // 如果是树枝边 
			dep[y] = dep[x] + 1;         // 计算深度 
			dfs(y, x);
			low[x] = min(low[x], low[y]);// 求最大程度追溯的节点 
			if (low[y] < dfn[x]) ++cnt;  // 有个儿子的返租边在 y 之上，注意这里是 < ，题目中说的是边 
		} else if (dfn[y] < dfn[x]) {    // 是返租边 
			if (dep[x] - dep[y] > 1) ans = ans * (dep[x] - dep[y] + 2); // 计算答案 
			++cnt;
			low[x] = min(low[x], dfn[y]);// 求最大程度追溯的节点 
		}
		if (cnt == 2) ok = 0;            // 不是仙人掌 
	}
}
int main() {
	ans = 1;
	n = read(), m = read();
	for (int i = 1, t, lst; i <= m; ++i) {
		t = read(), lst = read();
		for (int j = 2, x; j <= t; ++j) {
			x = read();
			e[++tot] = x, ne[tot] = he[lst], he[lst] = tot;
			e[++tot] = lst, ne[tot] = he[x], he[x] = tot;
			lst = x;
		}
	}
	tot = 0;
	dfs(1, 1);
	if (num != n) ok = 0;               // 不连通    
	if (ok) ans.pr();
	else puts("0");
	return 0;
}

后记

建议先写主体部分再加高精板子，要不然很难知道是哪里出了问题。用 int 能有 $70$ 分。