题目描述江爷爷给你出了一道题：给你一个图，保证每个点最多属于一个简单环，每个点度数最多为3，求这个图有多少“眼镜图形个数”保证图联通哦~其中“眼镜图形个数”，定义为三元组(x,y,S)，其中x和y表示图上的两个点，S表示一条x到y的简单路径，而且必须满足：1.x和y分别在两个不同的简单环上2.x所在的简单环与路径S的所有交点仅有x，y所在的简单环与路径S的所有交点仅有y。(x,y,S)与(y,x,S)算同一个眼镜如果你无法理解，可以参考样例。保证图是联通的输入输出格式输入格式：第一行两个数n和m之后m行，每行两个数x，y表示x和y之间有一条边。输出格式：输出一个数，表示眼镜的个数对19260817取膜的结果输入输出样例输入样例#1：说明样例#3，#4，#5，#6见下发的文件非常抱歉，出了点小锅，sample5.out好像是空文件，应该是6734568【子任务】11 121 22 33 44 55 14 66 77 88 99 1010 1111 7输出样例#1：1输入样例#2：14 161 22 33 44 13 55 66 77 88 99 69 1313 1413 1010 1111 1212 10输出样例#2：4子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。测试点编号 n的范围 m的范围 特殊性质测试点1 n <= 10 m <= 20测试点2 n <= 20 m <= 40测试点3 n <= 20 m <= 40测试点4 n <= 2000 m <= 4000测试点5 n <= 2000 m <= 4000测试点6 n <= 1000000 m <= 2000000 简单环个数 <= 2000测试点7 n <= 1000000 m <= 2000000 简单环个数 <= 2000测试点8 n <= 1000000 m <= 2000000测试点9 n <= 1000000 m <= 2000000测试点10 n <= 1000000 m <= 2000000
分析：有环在是不好处理的，先把所有环给缩成一个点.观察样例可以发现，如果环与环中间还有x个环，那么实际上这两个点可以构成2^x个眼镜，因为中间的每个环既可以走上面也可以走下面.于是dfs缩点似乎可以拿70分.
其实一个眼镜中间的圆点可以看做根节点，两个镜框可以看做是树，那么我们可以以1号点为根节点来建一棵树来进行树形dp.记录的状态不能是以i为根的子树的眼镜数，因为这样不好转移，应该将状态定义为半眼镜数.对于环和圆点要分别讨论，每个环可以看做是两条路径，所以在统计答案或者更新f的时候都要*2,因为每个子树是独立的，最后要把它们合并到一起，这里利用乘法原理来解决.可以得到f[x] = Σf[son[x]],if x为环 then f[x] = f[x] * 2 + 1,因为子树的可以走两个方向，自己也可以当做一个半眼镜的端点，合并子树的时候ans += f[x] * f[son[x]],if x是环 then ans += f[x] * f[son[x]].因为f[x]随着子节点的处理越来越大，所以答案不会遗漏.
#include#include #include #include using namespace std;const int maxn = 1000010, maxm = 4000010, mod = 19260817;int n, m, head[maxn], nextt[maxm], to[maxm], tot = 1, cnt, fa[maxn], scc[maxn], limit;int head2[maxn], to2[maxm], nextt2[maxm], tot2 = 1;bool vis[maxn];long long ans, f[maxn];void add(int x, int y){ to[tot] = y; nextt[tot] = head[x]; head[x] = tot++;}void add2(int x, int y){ to2[tot2] = y; nextt2[tot2] = head2[x]; head2[x] = tot2++;}void find(int x, int y){ scc[x] = cnt; if (x == y) return; find(fa[x], y);}void dfs(int u){ vis[u] = 1; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (v == fa[u] || scc[v]) continue; if (vis[v]) { cnt++; find(u, v); } else { fa[v] = u; dfs(v); } }}void build(int u){ vis[u] = 1; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (v == fa[u] || vis[v]) continue; if (scc[u] != scc[v]) { add2(scc[u], scc[v]); add2(scc[v], scc[u]); } build(v); }}void solve(int u, int from){ f[u] = 0; for (int i = head2[u]; i; i = nextt2[i]) { int v = to2[i]; if (v == from) continue; solve(v, u); long long temp = f[u] * f[v] % mod; if (u <= limit) temp *= 2; ans = (ans + temp) % mod; f[u] = (f[u] + f[v]) % mod; } if (u <= limit) { ans = (ans + f[u]) % mod; f[u] = (f[u] * 2 + 1) % mod; }}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } dfs(1); limit = cnt; for (int i = 1; i <= n; i++) if (!scc[i]) scc[i] = ++cnt; memset(vis, 0, sizeof(vis)); build(1); solve(1, 0); printf("%lld\n", ans); return 0;}