NC23482（小A的最短路 ）

感受



思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
const ll mod = 998244353;
struct edge{
    int v, nex;
}e[maxn << 1];
int fa[maxn][25];///fa[u][i] u向上跳2^i层所在的节点编号
int dep[maxn];
int head[maxn], cnt, n;
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1;
    }
}
void dfs(int u, int f, int d){
    int v; dep[u] = d;
    fa[u][0] = f;
    for(int i = 1; i <= 20; i++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dfs(v, u, d + 1);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int d = dep[u] - dep[v], i = 0; d; d >>= 1, i++){
        if(d & 1) u = fa[u][i];
    }
    /**u与v等深度*/
    if(u == v) return u;
    for(int i = 20; i >= 0; i--){
        if(fa[u][i] != fa[v][i]){
            u = fa[u][i]; v = fa[v][i];
        }
    }
    return fa[u][0];
}
int get(int x, int y){
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int main(){
    scanf("%d", &n);
    init();
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs(1, 0, 1);
    scanf("%d%d", &u, &v);
    int q, x, y;
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &x, &y);
        int ans = get(x, y);
        ans = min(ans, get(x, u) + get(v, y));
        ans = min(ans, get(x, v) + get(u, y));
        printf("%d\n", ans);
    }
    return 0;
}