cf1763 —F. Edge Queries

F. Edge Queries

https://codeforces.ml/contest/1763/problem/F

题意

n个点m条边的无向图，保证一个点不会存在多个连通分量中，q次询问，问对于从u到v的所有路径上的边，删掉一条边不影响u和v的连通性，问这样的边有多少条

思路

先进行边双缩点，因为在在同一个连通分量中的两个点至少存在两条路径。
那么容易得到，答案差不多就是u, v所在缩点之间的路径上所有连通分量的大小和(该大小指的是连通分量的边数)。
求一条路径上所有点的权值和
我们可以缩完点后建棵树 然后dfs求得每个点到根节点路径上的点权和 在用lca求即可

但还需要注意很多细节：
1.设a, b, c为u到v的路径上连续的三个连通分量，如果a和c连在b中的同一节点，那么b的大小不能被算进来
对于判断两个连通分量是否连接于同一节点 我们可以记录每个连通分量连向父亲的边的两个端点来做比较
2.考虑u和v恰好是连通分量的连接点，那么u和v所在的那个连通分量也不能被算进来
3.考虑求u, v的lca后，连在lca那个连通分量的同一个点 那么lca的大小不能被算进来
4.考虑特判 u == v和u, v在同一连通分量的情况

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long
#define int ll
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const ll mod = 1e9 + 7;

int n, m;
int low[N], dfn[N], tot, ec, c[N], sz[N], val[N];
int uu[N], vv[N];
pair<int, int>edge[N];
vector<int>g[N], g2[N];
stack<int>st;

//边双缩点
void tarjan(int x, int fa){
	dfn[x] = low[x] = ++tot;
	st.push(x);

	for(auto to : g[x]){
		if(!dfn[to]) {
			tarjan(to, x);
			low[x] = min(low[to], low[x]);
		}
		else if(to != fa)
			low[x] = min(low[x], dfn[to]);
	}

	if(dfn[x] == low[x]){
		ec++;
		while(1){
			int now = st.top();
			st.pop();
			c[now] = ec;
			if(now == x) break;
		}
	}
}

void init(){
	for(int i = 1; i <= n; i++){
		g[i].clear();
		g2[i].clear();
		low[i] = dfn[i] = 0;
		c[i] = 0;
		sz[i] = 0;
		val[i] = 0;
	}
	ec = 0;
	tot = 0;
}

//求LCA板子
ll fa[N][32], dep[N];
void dfs(ll x, ll pre, ll d)//找到每个节点父亲与深度
{
	fa[x][0] = pre;
	dep[x] = d;
	for (auto to : g2[x]){
		if (to != pre)
			dfs(to, x, d + 1);
	}
}

ll LCA(ll u, ll v)
{
	if (dep[u] > dep[v])
		swap(u, v);
	ll temp = dep[v] - dep[u];
	//cerr << "?" << v << " " << ans << "\n";
	for (ll i = 0; ((1ll << i) <= temp); i++)//将u v移到同一深度
	{
		if ((1ll << i) & temp){
			v = fa[v][i];
			//cerr << "?" << v << " " << ans << "\n";
		}
	}

	if (u == v)
		return u;

	for (ll i = log2(ec); i >= 0; i--)//两个节点一起往上走
	{								 //最多合法的跳跃是 2 ^ log2(n)
		if (fa[u][i] != fa[v][i])//如果相同则代表跳的太多了
		{
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

void init2()
{
	dfs(1, -1, 0);
	for (ll j = 0; (1ll << j) <= ec; j++)//预处理出每个节点往上走2^j所到的节点，超过根节点记为-1
	{
		for (ll i = 1; i <= ec; i++)
		{
			if (fa[i][j] < 0){
				fa[i][j + 1] = -1;
			}
			else {
				fa[i][j + 1] = fa[fa[i][j]][j];
			}
		}
	}
}

//求每个连通分量到根的路径上所有连通分量的大小和
void dfs_val(int x, int fa){
	val[x] = sz[x];
	if(fa > 0){
		val[x] += val[fa];
		if(uu[x] == vv[fa])
			val[x] -= sz[fa];
	}

	for(auto to : g2[x]){
		if(to == fa) continue;
		dfs_val(to, x);
	}
}

//找到某个点祖先的儿子
int get_secfa(int x, int d){
	for(int i = 31; i >= 0; i--){
		if((1ll << i) & d)
			x = fa[x][i];
	}
	return x;
}

void solve()
{
	cin >> n >> m;
	init();

	for(int i = 1, u, v; i <= m; i++){
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		edge[i] = {u, v};
	}

	tarjan(1, -1);
	
	// cerr << "???";
	// for(int i = 1; i <= n; i++)
	// 	cerr << c[i] << " ";
	// cout << "\n\n";

	for(int i = 1; i <= m; i++){
		int u = edge[i].first;
		int v = edge[i].second;
		if(c[u] == c[v]) sz[c[u]]++;
		else {
			g2[c[u]].push_back(c[v]);
			g2[c[v]].push_back(c[u]);
		}
	}
	init2();
        
        //求每个连通分量联想父亲的边的两个节点 uu vv
	for(int i = 1; i <= m; i++){
		int u = edge[i].first;
		int v = edge[i].second;
		if(c[u] != c[v]){
			int fu = c[u];
			int fv = c[v];
			if(dep[fu] > dep[fv]) {
				swap(fu, fv);
				swap(u, v);
			}

			uu[fv] = u;
			vv[fv] = v;
		}
	}

	dfs_val(1, -1);
	// for(int i = 1; i <= n; i++)
	// 	cerr << sz[i] << " ";

	int q;
	cin >> q;
	for(int i = 1; i <= q; i++){
		int a, b, x, y;
		cin >> x >> y;
		if(x == y){
			cout << 0 << "\n";
			continue;
		}
		a = c[x];
		b = c[y];
		if(a == b) cout << sz[a] << "\n";
		else {
			int ans = 0;
			if(dep[a] > dep[b]) {
				swap(a, b);
				swap(x, y);
			}
			int lc = LCA(a, b);
	
			if(lc == a){
				ans = val[b] - val[a] + sz[a];
				int dis = dep[b] - dep[a] - 1;
				int secfa = get_secfa(b, dis);
				//情况1
				if(uu[secfa] == vv[lc]) ans += sz[lc];
                                
                                //情况2
				if(vv[b] == y) ans -= sz[b];
				if(uu[secfa] == x) ans -= sz[a];
			}
			else{
				ans = val[a] + val[b] - val[lc] * 2 + sz[lc];
				int dis1 = dep[a] - dep[lc] - 1;
				int dis2 = dep[b] - dep[lc] - 1;
				int secfa1 = get_secfa(a, dis1);
				int secfa2 = get_secfa(b, dis2);
                                //情况1
				if(uu[secfa1] == vv[lc]) ans += sz[lc];
				if(uu[secfa2] == vv[lc]) ans += sz[lc];
                                //情况3
				if(uu[secfa1] == uu[secfa2]) ans -= sz[lc];
                                //情况2
				if(vv[a] == x) ans -= sz[a];
				if(vv[b] == y) ans -= sz[b];
			}
			cout << ans << "\n";
		}
	}
}


signed main()
{
	IOS;
	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
}