倍增法lca

随便寫一個裸的倍增法模闆

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> ve[100005];
int dep[100005];
int f[100005][21];
void inta(int x, int fa)  //初始化dep 和f 數組
{
    dep[x] = dep[fa] + 1;
    for (int i = 0; i <= 19; i++) {
        f[x][i + 1] = f[f[x][i]][i];//預處理出每個點的前倍增節點
    }
    for (int i = 0; i < ve[x].size(); i++) {
        int tmp = ve[x][i];
        if (tmp == fa)
            continue;//防止一條邊走兩次
        f[tmp][0] = x;//第一個點手動添加
        inta(tmp, x);
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);  //確定x比較深
    for (int i = 20; i >= 0; i--) {
        int tmp = f[x][i];
        if (dep[tmp] >= dep[y])//先将兩點調到同一深度
            x = tmp;
        if (x == y)
            return x;
    }
    for (int i = 20; i >= 0; i--) {//枚舉向上倍增
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }
    return f[x][0];
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int temp1, temp2;
        scanf("%d%d", &temp1, &temp2);
        ve[temp1].push_back(temp2);
        ve[temp2].push_back(temp1);
    }
    inta(1, 0);
    int q;
    scanf("%d", &q);
    while (q--) {
        int temp1, temp2;
        scanf("%d%d", &temp1, &temp2);
        int temp3 = lca(temp1, temp2);
        // cout<<temp3<<endl;
        printf("%d
", dep[temp1] + dep[temp2] - 2 * dep[temp3]);
    }
}
           

求lca的題目當作模闆