#C240219E. 铁人两项

标签（Label）

tarjan
模板

网址（Website）

$\qquad$ P4630 [APIO2018] 铁人两项

题解（Solution）

思路：

一、

$\qquad$看起来非常的复杂，并没有什么思路，于是开始看部分分。

$\qquad$其中有一个树的情况。对于一棵树，我们可以先确定一个固定的点，然后从这个点开始 $dfs$ ，在半路上计算从最开始的点 $x$ ，走到当前点 $y$ 中的路径条数，时间复杂度 $O(n^2)$ 。换一个思路，如果以枚举中间的点（设为 $x$ ），那么我们可以通过在求其子树的大小 $siz[x]$ 的时候计算出经过当前点的路径条数。

$\qquad$（懂了的可以跳过此段）当扫到点 $x$ 时，先初始化 $siz[x]$ ，求出其第一棵子树的 $siz$ ，然后路径条数便是 $2siz[x]siz[y_1]$ （从 $a$ 到 $b$ 与从 $b$ 到 $a$ 是不一样的），计入 $siz[y1]$ 的大小以后，再用此时的 $siz[x]$ 乘上下一个子树的 $siz[y_2]$ ，以此类推。最后，求出所有子树的 $siz$ 之和后，再将其与 $x$ 点上面的点的数量相乘，即 $ans+=2siz[x](num-siz[x])$ （其中 $num$ 为该连通块的大小）。

$\qquad$于是我们可以在 $O(n)$ 的时间内求出树上的路径条数。

二、

$\qquad$考虑到每一条路径都是简单路径，所以对于无向图中的任意割点，其所属的点双连通分量中的点要是想互相连通，路上就必须走这个割点，容易联想到圆方树（这里用的是广义圆方树，会将所有的点双连通分量变成方点），直接将无向图转换为森林，便可以很好的解决这个问题。

$\qquad$对于森林中的每一棵树，我们可以将每一个点双连通分量看作一个整体，则答案的计算变成了求 $ans+=2\cdot siz[x]\cdot siz[y]\cdot w[x]$ （$w[x]$ 表示的是当前点双的点数），由于每一个点双连通分量计算点的个数的时候都包含了它的割点，因此我们在计算贡献的时候会把割点多计算一次，因此我们需要考虑如何去除这个影响，由于最终计算出来的路径都会乘上当前点双中点的个数，所以我们可以直接选择将所有的圆点的 $w[x]$ 赋值为 $-1$ ，然后将所有方点对应的点的个数赋值为当前点双的点的个数。

$\qquad$根据圆方树的性质，对于两点 $x,y$ ，它们在原图中所有简单路径经过的点集之并，等于圆方树路径上经过的所有方点的相邻圆点之和。由此，对于一条在圆方树上的路径（从一个圆点到另一个圆点），其经过的点的权值和刚好就是 “ 在原图中点 $x,y$ 所经过的路径的点集之并的大小 $-2$ ”（自己都要被搞晕了），刚好就是题目中以点 $x,y$ 为起点和终点的点对的数量。

$\qquad$转换成固定点对中中间经过的点 $c$（即 $(s,c,f)$ 中的 $c$ ），这种方法同样适合，只需要将计算出的圆方树上当前圆点的路径数乘上当前点的点权就好啦~

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;

vector<int> ft[N];
stack<int> st;

int n,m,ans;
int w[N];

int dfn[N],low[N],t;
int scc_cnt,num;
vector<int> tr[N];
void tarjan(int x){
	dfn[x]=low[x]=++t,num++;
	st.emplace(x),w[x]=-1;
	for(auto y:ft[x]){
		if(!dfn[y]){
			tarjan(y) , low[x] = min(low[x],low[y]);
			if(dfn[x] == low[y]){
				scc_cnt++;
				while(st.top() != y){
					tr[st.top()].emplace_back(scc_cnt);
					tr[scc_cnt].emplace_back(st.top());
					w[scc_cnt]++;st.pop();
				}st.pop();w[scc_cnt]+=2;
				tr[y].emplace_back(scc_cnt),tr[scc_cnt].emplace_back(y);
				tr[x].emplace_back(scc_cnt),tr[scc_cnt].emplace_back(x);
			}
		}else low[x] = min(low[x],dfn[y]);
	}
}

int siz[N];
void dfs_ans(int x,int fa){
	siz[x] = x <= n;
	for(auto y:tr[x]){
		if(y == fa) continue;
		dfs_ans(y,x);
		ans += 2 * siz[x] * siz[y] * w[x];
		siz[x] += siz[y];
	}ans += 2 * siz[x] * (num - siz[x]) * w[x];
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;For(i,1,m){
		int x=input(),y=input();
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}int Tim = clock();
	
	scc_cnt=n;
	
	For(i,1,n) if(!dfn[i]) tarjan(i),dfs_ans(i,0),num=0;
	
	cout<<ans<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1024.,0;
}