最短路-（生成树+最短路+LCA）

题目描述
n 个点，m条边， q个询问 ，每次输出 x,y的最短距离

思路
首先看一个弱化版的
给你n个点 ，n-1条边构成一颗树，q个询问，每次输出树上两点x,y的距离

这个题就是一个裸的LCA，lca的dfs完之后可以直接输出

int dis(int x, int y) {
    return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}

这个题 的 1≤ m≤ n+100 也就是说 多出来了100条边 就是 唯一的不同之处

我们先假设用其中的n-1条边构造一颗树，跑一边LCA ，求出q个询问中的

    ans[i] = dis(x, y);

然后我们把剩余的边在加入的这颗树中，看看会不会对 答案产生影响，也就是说ans[i] 会不会变的更小

我们设加入的这条边 的 两个端点为 x,y。 现在我们要看这条边的加入会不会对第一个询问dis(q1x,q1y)产生影响

只需要比较 dist[x][q1x]+dist[x][q1y]是否比ans[i]小就可以了 ，看 y点和看x点都可以

这100条边的处理方式直接跑单源最短路就可以了，一共才100次

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 4e5 + 170;
const ll mod = 1000000007;

#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)

inline ll read() {
    ll x = 0;
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || '9' < ch) f |= ch == '-', ch = getchar();
    while ('0' <= ch && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return f ? -x : x;
}

void out(ll x) {
    int stackk[20];
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (!x) {
        putchar('0');
        return;
    }
    int top = 0;
    while (x) stackk[++top] = x % 10, x /= 10;
    while (top) putchar(stackk[top--] + '0');
}

int head[maxn], cnt, n, m, dist[maxn], vis[maxn], ans[maxn];
int p[maxn], depth[maxn], fa[maxn][32], length, q;
vector<PII> g;

int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

struct wmy {
    ll u, v, w, next;
} a[maxn];
struct node {
    ll u, v;
} b[maxn];

void add(ll u, ll v, ll w) {
    a[cnt].u = u;
    a[cnt].v = v;
    a[cnt].w = w;
    a[cnt].next = head[u];
    head[u] = cnt++;
}
int num;
void bfs(int st) {
    num++;
    mst(dist,inf);
    queue<int > qq;
    dist[st] = 0;
    qq.push(st);
    while (qq.size()) {
        int  dian = qq.front();
        qq.pop();

        for (int i = head[dian]; ~i; i = a[i].next) {
            if (dist[a[i].v] > a[i].w + dist[dian]) {
                dist[a[i].v] = a[i].w + dist[dian];
                qq.push(a[i].v);
            }
        }

    }

    for (int i = 1; i <= q; i++)
        ans[i] = min(ans[i], dist[b[i].v] + dist[b[i].u]);

}

void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    fa[u][0] = p;
    for (int i = 1; i <= length; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; ~i; i = a[i].next) {
        ll v = a[i].v;
        if (v == p) continue;
        dfs(v, u);
    }
}

int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = length; i >= 0; i--)
        if (depth[fa[x][i]] >= depth[y]) x = fa[x][i];
    if (x == y) return x;

    for (int i = length; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}

int dis(int x, int y) {
    return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}
int main() {
    mst(head, -1);
    mst(dist,inf);
    n = read(), m = read();
    length = log2(n) + 1;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= m; i++) {
        ll u = read();
        ll v = read();
        if (find(u) != find(v)) {
            add(u, v, 1);
            add(v, u, 1);
            p[find(u)] = find(v);
        } else {
            g.push_back({u, v});
        }
    }

    dfs(1, 0);

    for (auto i:g) {
        add(i.first,i.second,1);
        add(i.second,i.first,1);
    }

    q = read();

    for (int i = 1; i <= q; i++) {
        ll x = read();
        ll y = read();
        b[i].u = x;
        b[i].v = y;
        ans[i] = dis(x, y);
    }
    for (auto i:g) {
        if(num>101) break;
        if(vis[i.first]==0)
            bfs(i.first),vis[i.first]=1;
    }
    for (int i = 1; i <= q; i++)
        out(ans[i]), puts("");
    return 0;
}


/*

*/