小A的最短路

题意： 给定一棵个点的树，边权均为，以及多出的一条边权为的边，询问树上两点之间的路径的最小权值。

题解： https://ac.nowcoder.com/acm/problem/19814 这道题的弱化版，只多出了一条边权为的边。
预处理树上倍增关系，然后加入这条边权为边，每次取直接在树上走的最短路权值和经过该条边的最短路权值的最小值即可。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

template<typename T>
inline T Read(){
    T s = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
    return s * f;
}

#define read() Read<int>()
#define readl() Read<long long>()

const int N = 3e5 + 10;
const int M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

const int Mdep = 20;
int dep[N];
int f[N][Mdep + 1];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for(int i = 1; i <= Mdep; ++i)
        f[u][i] = f[f[u][i - 1]][i - 1];

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(v == fa) continue;
        dfs(v, u);
    }
}

int LCA(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);

    for(int i = Mdep; i >= 0; i--)
        if(dep[f[a][i]] >= dep[b]) a = f[a][i];
    if(a == b) return a;

    for(int i = Mdep; i >= 0; i--)
        if(f[a][i] != f[b][i]) a = f[a][i], b = f[b][i];
    return f[a][0];
}

int dis(int a, int b) {
    return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
}

int q[N];
int dist[N];
void bfs(int a, int b) {
    memset(dist, 0x3f, sizeof dist);
    dist[a] = 0;
    int hh = 0, tt = -1;
    q[++tt] = a;

    while(hh <= tt) {
        int u = q[hh++];
        for(int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            int distance = 1;
            if((u == a && v == b) || (u == b && v == a)) distance = 0;
            if(dist[v] > dist[u] + distance) {
                dist[v] = dist[u] + distance;
                q[++tt] = v;
            }
        }
    }
} 

void solve() {
    memset(h, -1, sizeof h);
    int n = read();
    for(int i = 1; i < n; ++i) {
        int a = read(), b = read();
        add(a, b), add(b, a);
    }

    dfs(1, 0);

    int a = read(), b = read();
    add(a, b), add(b, a);

    bfs(a, b);

    int Q = read();
    while(Q--) {
        int x = read(), y = read();
        int res = min(dis(x, y), dist[x] + dist[y]); 
        printf("%d\n", res);
    }
}

int main()
{
    int T = 1;
    //T = read();
    for(int i = 1; i <= T; ++i) {
        solve();
    }
}