一、题目描述：
给你一个 $n$ 个点，$m$ 条边的无向图。图不一定联通
求出点对 $( u,c,v )$ 的数量，使得点 $u$ 存在一条经过点 $c$ 到达点 $v$ 的无向图。
数据范围：$1 \le n \le 1 \times 10^5,1 \le m \le 2 \times 10^5$
二、解题思路：
算是圆方树比较模板的题了吧。
首先化成树/森林，有环的话不好统计。
考虑固定两个点，求中间点的个数。
很明显同一个环上的任意两点可以通过环上其其它任意点到达彼此。
如果两个点的路径上有环则这个环上的所有点都可以作为中间点。
感觉就是求路径上方点的度数了，但是出现每个点会重复统计统计在两个方点内。
所以我们可以将圆点值赋为 $-1$，将方点的权值赋为它的度数。刚好也消除掉两个端点带来的影响。
于是转化为统计圆方树上任意两圆点之间的路径权值和，经典问题了。时间复杂度 $O(n+m)$。
三、完整代码：
1 #include<iostream>
2 #include<vector>
3 #define N 200010
4 using namespace std;
5 long long ans;
6 int n,m,r,cc,tot;
7 vector <int> e1[N],e2[N];
8 int s[N],res[N],vis1[N],vis2[N];
9 int q[N],du[N],dfn[N],low[N],val[N];
10 void tarjan(int u)
11 {
12 dfn[u]=low[u]=++tot;q[++r]=u;
13 for(int to:e1[u])
14 {
15 if(!dfn[to]){
16 tarjan(to),low[u]=min(low[u],low[to]);
17 if(low[to]>=dfn[u]){
18 cc++;du[cc]+=2;
19 du[to]++,du[u]++;
20 e2[cc].push_back(u);
21 e2[u].push_back(cc);
22 e2[cc].push_back(to);
23 e2[to].push_back(cc);
24 while(q[r]^to){
25 e2[cc].push_back(q[r]);
26 e2[q[r]].push_back(cc);
27 du[q[r]]++,du[cc]++;r--;
28 }r--;
29 //弹栈的时候不要把 u 也弹出来了
30 }
31 }else low[u]=min(low[u],dfn[to]);
32 }
33 }
34 void dfs1(int u,int ff)
35 {
36 s[u]=u<=n;vis1[u]=1;
37 for(int to:e2[u])
38 if(to!=ff)
39 dfs1(to,u),s[u]+=s[to];
40 }
41 void dfs2(int u,int ff)
42 {
43 if(ff) res[u]=res[ff]+s[ff]-s[u];vis2[u]=1;
44 if(u<=n){
45 int sum=res[u]+s[u]-1;ans-=sum*2;
46 for(int to:e2[u])
47 if(to!=ff)
48 ans-=1ll*s[to]*(sum-s[to]);
49 //记得要判定 to!=ff
50 ans-=1ll*res[u]*(sum-res[u]);
51 }else{
52 int sum=res[u]+s[u];
53 for(int to:e2[u])
54 if(to!=ff)
55 ans+=1ll*du[u]*s[to]*(sum-s[to]);
56 //记得要判定 to!=ff
57 ans+=1ll*du[u]*res[u]*(sum-res[u]);
58 }
59 for(int to:e2[u])
60 if(to!=ff) dfs2(to,u);
61 //记得要判定 to!=ff
62 }
63 int main()
64 {
65 ios::sync_with_stdio(false);
66 cin.tie(0);cout.tie(0);
67 cin>>n>>m;cc=n;
68 for(int i=1,u,v;i<=m;i++)
69 {
70 cin>>u>>v;
71 e1[u].push_back(v);
72 e1[v].push_back(u);
73 }
74 for(int i=1;i<=n;i++)
75 if(!dfn[i]) tarjan(i);
76 for(int i=1;i<=cc;i++)
77 if(!vis1[i])
78 dfs1(i,0);
79 //注意图不连通
80 for(int i=1;i<=cc;i++)
81 if(!vis2[i])
82 dfs2(i,0);
83 //注意图不连通
84 cout<<ans<<'\n';
85 return 0;
86 }
四、写题心得：
好！第一道圆方树的题，很妙，很高兴！收获经验如下：
$1、彻底了解了建圆方树的过程。=> Exp++!$
$2、图如果不连通，判定父亲边上点的个数方法有变，如上。=> Exp++! $
$3、vector\ 好像确实有点慢，链式前向星好快，以后少用\ vector => Exp++$
标签：P4630,cc,题解,APIO2018,back,++,int,low,push From： https://www.cnblogs.com/yhy-trh/p/P4630.html