蒟蒻调了巨久终于调出来了。
题目大意 给出一个基环树，求树中的简单路径数目。
经过观察我们可以发现，在一个环中从一个点到另一个点有两条路径，但在树中从一个点到另一个点就只有一条路径。
所以我们不妨用一个容斥的思想，先把两个点之间的路径都设为两条，然后排除那些不正确的。
那么便是n*(n-1)-∑s*(s-1)/2 其中（n为所给的点的数目，s为每一棵树中点的数目）
那么我们的首要目标先是找环，然后枚举环上的每一个点来查找每一棵树的节点数。
找环我用的是tarjan缩点，然后用一个dfs查找节点数。
#include<iostream> #include<algorithm> #include<stack> using namespace std; const int maxx = 200005; long long head[maxx], now, dfn[maxx], low[maxx], vis[maxx], it, sd[maxx], all[maxx], book[maxx]; long long ans = 0, l = 0; stack<int>q; struct edge { int nex, to; }a[maxx*2]; void add_edge(int at, int to) { a[++now].nex = head[at]; a[now].to = to; head[at] = now; } void tarjan(int x,int fa) { dfn[x] = low[x] = ++it; vis[x] = 1; q.push(x); for (int i = head[x]; i; i = a[i].nex) { if (a[i].to != fa) { int to = a[i].to; if (!vis[to]) { tarjan(to, x); low[x] = min(low[x], low[to]); } else low[x] = min(low[x], low[to]); } } if (dfn[x] == low[x]) { int y; while (y = q.top()) { q.pop(); sd[y] = x; vis[y] = 0; if (y == x)break; } } } void dfs(int at,int fa) { book[at] = 1; l++; for (int i = head[at]; i; i = a[i].nex) { int to = a[i].to; if (!book[to] && to != fa) dfs(to, at); } } int main() { int t; cin >> t; while (t--) { now = 0,it=0; long long n, maxx = 0, p = 0; cin >> n; ans = n * (n - 1); for (int i = 1; i <= n; i++) { int at, to; cin >> at >> to; add_edge(at, to); add_edge(to, at); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i); for (int i = 1; i <= n; i++) { all[sd[i]]++; if (all[sd[i]] > maxx) { p = sd[i]; maxx = all[sd[i]]; } } for (int i = 1; i <= n; i++) if (sd[i] == p) book[i] = 1; for (int i = 1; i <= n; i++) { if (book[i]) { l = 0; dfs(i, i); ans -= (l * (l - 1) / 2); } } cout << ans << endl; for (int i = 1; i <= n; i++) { sd[i] = dfn[i] = low[i] = vis[i] = all[i] = head[i] = book[i] = 0; } } return 0; }
CodeForces 1454E Number of Simple Paths
原文：https://www.cnblogs.com/redintoncforever/p/14501410.html