54pts tarjan+LCA 求调

#include<bits/stdc++.h>
using namespace std ;
const int kMaxN = 1e4 + 5 , kMaxM = 5e4 + 5 ;
struct node
{
  int v , nxt ;
}a[kMaxM << 1] ;
struct Edge
{
  int u , v ;
}edge[kMaxM << 1] ;
map<pair<int , int> , bool> mp ;
int n , m , q ;
int tim , cnt = 1 , scc ;
int dfn[kMaxN] , low[kMaxN] , head[kMaxN] , color[kMaxN] , dep[kMaxN] , dp[kMaxN][20] ;
bool vis[kMaxN] , fl[kMaxN] ;
stack<int> st ;
vector<int> vans[kMaxN] ;
void add(int u , int v)
{
  a[++cnt] = {v , head[u]} ;
  head[u] = cnt ;
}
void tarjan(int u , int fa)
{
  dfn[u] = low[u] = ++tim ;
  vis[u] = 1 ;
  st.push(u) ;
  for( int i = head[u] ; i ; i = a[i].nxt )
  {
    int v = a[i].v ;
    if(i == fa) continue ;
    if(!dfn[v])
    {
      tarjan(v , i ^ 1) ;
      low[u] = min(low[u] , low[v]) ;
    }
    else if(vis[v])
    {
      low[u] = min(low[u] , dfn[v]) ;
    }
  }
  if(dfn[u] == low[u])
  {
    scc++ ;
    while(!st.empty())
		{
      color[st.top()] = scc ;
			vis[st.top()] = 0 ;
			if(u == st.top())
			{
				st.pop() ;
				break ;
			}
			st.pop() ;
		}
  }
}
// void dfs(int u)
// {
//   if(dp[u] != -1) return ;
//   dp[u] = siz[u] ;
// 	int maxn = 0 ;
// 	for( int i = head[u] ; i ; i = a[i].nxt )
// 	{
// 		int v = a[i].v ;
// 		if(dp[v] == -1)
// 		{
// 			dfs(v) ;
// 		}
// 		maxn = max(maxn , dp[v]) ;
// 	}
// 	dp[u] += maxn ;
// }
void write(int x)
{
  if(x == 1) cout << 1 ;
  else if(x == 0) cout << 0 ;
  else
  {
    write(x >> 1) ;
    cout << x % 2 ;
  }
}
void dfs(int u , int fa)
{
  dep[u] = dep[fa] + 1 ;
  dp[u][0] = fa ; 
  fl[u] = 1 ;
  for( int i = 1 ; (1 << i) <= dep[u] ; i++ )
  {
    dp[u][i] = dp[dp[u][i - 1]][i - 1] ;
  }
  for( int i = head[u] ; i ; i = a[i].nxt )
  {
    int v = a[i].v ;
    if(fl[v]) continue ;
    dfs(v , u) ;
  }
}
int lca(int x , int y)
{
  if(dep[x] > dep[y]) swap(x , y) ;
	for( int i = 20 ; i >= 0 ; i-- )
	{
		if(dep[dp[y][i]] >= dep[x]) y = dp[y][i] ;
	}
	if(y == x)
	{
		return x ;
	}
	for( int i = 20 ; i >= 0 ; i-- )
	{
		if(dp[y][i] != dp[x][i]) y = dp[y][i] , x = dp[x][i] ;
	}
	return dp[x][0] ;
}
void solve()
{
  cin >> n >> m ;
  for( int i = 1 ; i <= m ; i++ )
  {
    cin >> edge[i].u >> edge[i].v ;
    if(edge[i].u == edge[i].v) continue ;
    if(edge[i].u > edge[i].v) swap(edge[i].u , edge[i].v) ;
    if(mp[{edge[i].u , edge[i].v}] == 1) continue ;
    else mp[{edge[i].u , edge[i].v}] = 1 ;
    add(edge[i].u , edge[i].v) ;
    add(edge[i].v , edge[i].u) ;
  }
  for( int i = 1 ; i <= n ; i++ )
  {
    if(!dfn[i])
    {
      tarjan(i , 0) ;
    }
  }
  cnt = 1 ;
  memset(head , 0 , sizeof head) ;
  mp.clear() ;
  for( int i = 1 ; i <= m ; i++ )
  {
    if(color[edge[i].u] != color[edge[i].v]) 
    {
      int cu = color[edge[i].u] , cv = color[edge[i].v] ;
      if(cu > cv) swap(cu , cv) ;
      if(mp[{cu , cv}] == 1) continue ;
      else mp[{cu , cv}] = 1 ;
      add(color[edge[i].u] , color[edge[i].v]) ;
      add(color[edge[i].v] , color[edge[i].u]) ;
    }
  }
  for( int i = 1 ; i <= n ; i++ )
  {
    if(!fl[i]) dfs(i , 0) ;
  }
  cin >> q ;
  while(q--)
  {
    int x , y ;
    cin >> x >> y ;
    int z = lca(color[x] , color[y]) ;
    // cout << dep[z] << " " ; 
    write((dep[color[x]] + dep[color[y]]) - (dep[z] * 2) + 1) ;
    cout << "\n" ;
  }
  // write(0) ;
  // cnt = 1 ;
  // memset(head , 0 , sizeof head) ;
  // for( int i = 1 ; i <= m ; i++ )
  // {
  //   if(color[edge[i].u] != color[edge[i].v])
  //   {
  //     add(color[edge[i].u] , color[edge[i].v]) ;
  //   }
  // }
  // memset(dp , -1 , sizeof dp) ;
  // int maxn = 0 ; 
  // for( int i = 1 ; i <= scc ; i++ )
  // {
  //   if(dp[i] == -1) dfs(i) ;
  //   maxn = max(maxn , dp[i]) ;
  // }
  // cout << maxn ;
  // memset(dp , -0x3f , sizeof dp) ;
  // dp[0] = 0 ;
  // for( int i = 1 ; i <= scc ; i++ )
  // {
  //   for( int j = w ; j >= sizc[i] ; j-- )
  //   {
  //     dp[j] = max(dp[j] , dp[j - sizc[i]] + sizd[i]) ;
  //   }
  // }
  // cout << dp[w] ;
}
int main()
{
  int t = 1 ;
  // cin >> t ;
  while(t--) solve() ;
  return 0 ;
}