#C241019B. 图的遍历

标签（Label）

• 圆方树

网址（Website）

题目详情 - 图的遍历 - Super

题解 - 图的遍历 - Super

题解（Solution）

出题者题解

算法分析

考虑点双缩树，$x$ 走到 $z$ 必须经过 $y$，当且仅当 $y$ 是割点，且 $x$ 和 $z$ 在 $y$ 的不同子树中。

分 $y$ 是否在 $x$ 子树两种情况讨论，每种情况都分别令 $O(1)$ 个 $dfs$ 序区间内的点不合法。

复杂度 $O(n \log n)$，有一种情况需要求 $x$ 的 $dep_y - dep_x - 1$ 级祖先，

fun fact： 这个题成为了签到题，前三题通过 $18, 12, 22$ 位选手。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#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
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;

vector<int> tt[N],ft[N];
int n,m;

int dfn[N],low[N],t;
stack<int> st;
int scc[N],cnt;
int f[N][32],dep[N];
void tarjan(int x,int fa){
	dfn[x] = low[x] = ++t;
	st.emplace(x);
	for(auto y:tt[x]){
		if(y==fa) continue;
		if(!dfn[y]){
			tarjan(y,x), low[x] = min(low[x], low[y]);
			if(dfn[x] <= low[y]){
				cnt++;
				ft[x].emplace_back(cnt);
				f[cnt][0] = x;
				int u;
				do{
					u = st.top();st.pop();
					scc[u] = f[u][0] = cnt;
					ft[cnt].emplace_back(u);
				}while(u!=y);
			}
		}else low[x] = min(low[x], dfn[y]);
	}
}

int L[N], R[N], idx;
int siz[N];
void dfs_siz(int x,int fa){
	L[x] = ++idx;
	siz[x] = x<=n, dep[x] = dep[fa]+1;
	For(j,1,18) f[x][j] = f[f[x][j-1]][j-1];
	for(auto y:ft[x]) if(y!=fa) dfs_siz(y,x), siz[x]+=siz[y];
	R[x] = idx;
}

int kth(int x,int k){
	For(j,0,18) if(k>>j&1) x = f[x][j];
	return x;
}

void Solve(){
	n = cnt = rd(), m = rd();
	For(i,1,n*2){
		ft[i].clear(), tt[i].clear();
		dfn[i]=low[i]=scc[i]=siz[i]=0;
	}while(st.size()) st.pop();
	t = 0, idx = 0;
	
	For(i,1,m){
		int x = rd(), y = rd();
		tt[x].emplace_back(y);
		tt[y].emplace_back(x);
	}tarjan(1,0);
	dfs_siz(1,0);
	int q = rd();
	while(q--){
		int res = 0, x = rd(), y = rd();
		if(L[x] > L[y]) swap(x,y);
		if(L[x] <= L[y] && R[y] <= R[x]){
			int f = kth(y,dep[y]-dep[x]-1);
			res = siz[f] - siz[y] + 2;
		}else res = n - siz[x] - siz[y] + 2;
		printf("%lld\n",res);
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
//	freopen("ex_travel1.in","r",stdin);
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	int T = rd(), Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}