题目
题意:在一个无向图里面选三个点\(s\),\(c\),\(f\)
需要能够从\(s\)出发，经过\(c\),到达\(f\)点，中间不能提前经过\(f\),且需要是一个简单路径
Solution:
简单路径当然就是园方树了，想想怎么统计答案
yy一下可以发现，有一条路径\(s\)，\(f\),中间能选的点就是路径上的圆点和
因为在一个点双连通分量里面，一定有一个不重复的路径到出点去。
想想怎么赋权，方点赋连接的圆点个数，圆点为-1，最后一条路径的权值和刚好就是去掉两个头的圆点个数，
然后就是个简单的dp计数了
code:
#include<bits/stdc++.h>
#define ll long long
#define R register
#define pb push_back
template<class T>
void rea(T &x)
{
int f(0);char ch=getchar();x = 0;
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x = f?-x:x;
}
using namespace std;
const int N = 500005;
vector<int> I[N], e[N<<1];
ll ans;
int n, m, node, num;
int dfn[N], low[N], dfc, sta[N], tp;
int val[N<<1], siz[N<<1];
bool vis[N<<1];
void tarjan(int x)
{
dfn[x] = low[x] = ++dfc;
sta[++tp] = x;
for(R int i = 0; i < I[x].size(); ++i)
{
if(!dfn[I[x][i]])
{
tarjan(I[x][i]);
low[x] = min(low[x], low[I[x][i]]);
if(low[I[x][i]] == dfn[x])
{
val[++node] = 1;
for(R int o = 0; o != I[x][i]; --tp)
{
o = sta[tp];
e[node].pb(o);
e[o].pb(node);
++val[node];
}
e[x].pb(node), e[node].pb(x);
}
}
else low[x] = min(low[x], dfn[I[x][i]]);
}
}
void cal(int x, int fa)
{
siz[x] = (x<=n);
//cout<<x<<" "<<val[x]<<endl;
for(R int i = 0; i < e[x].size(); ++i) if(e[x][i] != fa)
{
cal(e[x][i], x);
ans += 2ll * siz[x] * siz[e[x][i]] * val[x];
siz[x] += siz[e[x][i]];
}
ans += 2ll * siz[x] * (num-siz[x]) * val[x];
}
int main()
{
rea(n), rea(m); node = n;
memset(val, -1, sizeof val);
int x, y;
for(R int i = 1; i <= m; ++i)
rea(x), rea(y), I[x].pb(y), I[y].pb(x);//读入用I！！
for(R int i = 1; i <= n; ++i)
if(!dfn[i]) num = dfc, tarjan(i), num = dfc-num, cal(i, 0);
printf("%lld\n", ans);
return 0;
}