[Luogu p4320] road meets (round square tree)

Road meets

Topic link ：luogu P4320

The main idea of the topic

Here's an undirected connected graph , No double edge self ring , Then I'll give you two points each time , Ask you how many points are necessary for the path between two points .

Ideas

Round square tree pre The template questions ？

How to make a round square tree is not mentioned here , Watch the blog of triathlon .

Then we know that the nature of the round square tree is that the dots and square dots are fixed , And the dot is the dot of the original drawing .
That means that the number of dots is the number of dots that must go , That is to say ( The number of chains +1)/2.
be without .

Code

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 5e5 + 100;
int n, m, q;
vector <int> G[N];

struct YF_tree {
    
	int dfn[N], low[N], deg[N << 1], fa[N << 1][21], sta[N], tot;
	vector <int> GG[N << 1];
	
	void link(int x, int y) {
    GG[x].push_back(y); GG[y].push_back(x);}
	
	void tarjan(int now) {
    
		dfn[now] = low[now] = ++dfn[0]; sta[++sta[0]] = now;
		for (int i = 0; i < G[now].size(); i++) {
    int x = G[now][i];
			if (!dfn[x]) {
    
				tarjan(x); low[now] = min(low[now], low[x]);
				if (dfn[now] == low[x]) {
    
					tot++;
					while (sta[sta[0]] != x) {
    
						link(tot, sta[sta[0]]);
						sta[0]--;
					}
					link(tot, sta[sta[0]]); sta[0]--;
					link(tot, now);
				}
			}
			else low[now] = min(low[now], dfn[x]);
		}
	}
	
	void dfs(int now, int father) {
    
		deg[now] = deg[father] + 1; fa[now][0] = father;
		for (int i = 1; i <= 20; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
		for (int i = 0; i < GG[now].size(); i++) {
    int x = GG[now][i];
			if (x != father) {
    
				dfs(x, now);
			}
		}
	}
	
	void Init() {
    
		tot = n;
		for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i), dfs(i, 0);
	}
	
	int LCA(int x, int y) {
    
		if (deg[x] < deg[y]) swap(x, y);
		for (int i = 20; i >= 0; i--)
			if (deg[fa[x][i]] >= deg[y]) x = fa[x][i];
		if (x == y) return x;
		for (int i = 20; i >= 0; i--) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
		return fa[x][0];
	}
	
	int quest(int x, int y) {
    
		int lca = LCA(x, y), dis = deg[x] + deg[y] - deg[fa[lca][0]] * 2;
		return (dis + 1) / 2;
	}
}T;

int main() {
    
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		G[x].push_back(y); G[y].push_back(x);
	}
	
	T.Init();
	
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		printf("%d\n", T.quest(x, y));
	}
	
	return 0;
}