P4630 [APIO2018] 铁人两项题解-526互联

一、题目描述：

　　给你一个 $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 }