学了一下圆方树， 好神奇的东西呀。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ull unsigned long longusing namespace std;const int N = 2e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-9;const double PI = acos(-1);int n, m, q;vector
         
           G[N];vector
          
            G1[N];int dfn[N], low[N], idx, nn;int stk[N], top;void tarjan(int u, int preid) { dfn[u] = low[u] = ++idx; stk[++top] = u; for(auto& e : G[u]) { if(e.se == preid) continue; int v = e.fi; if(!dfn[v]) { tarjan(v, e.se); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) { nn++; G1[u].push_back(nn); G1[nn].push_back(u); do { G1[stk[top]].push_back(nn); G1[nn].push_back(stk[top]); } while(stk[top--] != v); } } else low[u] = min(low[u], dfn[v]); }}int f[N][20], depth[N];void dfs(int u, int fa) { depth[u] = depth[fa] + 1; f[u][0] = fa; for(int i = 1; i < 20; i++) f[u][i] = f[f[u][i - 1]][i - 1]; for(auto& v : G1[u]) { if(v == fa) continue; dfs(v, u); }}int getLca(int u, int v) { if(depth[u] < depth[v]) swap(u, v); for(int i = 19; i >= 0; i--) if(depth[f[u][i]] >= depth[v]) u = f[u][i]; if(u == v) return u; for(int i = 19; i >= 0; i--) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0];}int main() { scanf("%d%d%d", &n, &m, &q); nn = n; for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(mk(v, i)); G[v].push_back(mk(u, i)); } for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i, -1); dfs(1, 0); while(q--){ int u, v; scanf("%d%d", &u, &v); int lca = getLca(u, v); printf("%d\n", (depth[u] + depth[v]) / 2 - depth[lca]); } return 0;}/**/