学了一下圆方树, 好神奇的东西呀.
- #include<bits/stdc++.h>
- #define LL long long
- #define fi first
- #define se second
- #define mk make_pair
- #define PLL pair<LL, LL>
- #define PLI pair<LL, int>
- #define PII pair<int, int>
- #define SZ(x) ((int)x.size())
- #define ull unsigned long long
- using 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<PII> G[N];
- vector<int> 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;
- }
- /*
- */
来源: http://www.bubuko.com/infodetail-3013771.html