Template. LCA Doubling Search

使用倍增法的做法來計算LCA。
先製作dp表，$dp[i][j]$代表$i$的第$2^j$祖先是誰，若不存在則為-1。
在查詢時，先將點$a$和$b$調整到相同高度，再一起慢慢往上移動尋找LCA。
時間複雜度：$O(N log N)$

#define maxn 1000
int n, logn; //logn = log2(n) + 1
vector<int> tree[maxn];
vector<int> dp[maxn];
int deep[maxn];
void init() {
    logn = log2(n) + 1;
    dfs(0, 0);
}
void dfs(int now, int parent) {
    dp[now].resize(logn);
    for (int i = 1; i < logn; i++)
        dp[now][i] = -1;
    dp[now][0] = parent;
    for (int i = 0; i + 1 < logn; i++)
        dp[now][i + 1] = dp[dp[now][i]][i];
    for (int i : tree[now]) {
        if (i == parent)
            continue;
        deep[i] = deep[now] + 1;
        dfs(i, now);
    }
}
int LCA(int a, int b) {
    if (deep[a] < deep[b])
        swap(a, b);
    for (int i = deep[a] - deep[b], k = 0; i; i >>= 1, k++)
        if (i & 1)
            a = dp[a][k];
    if (a == b)
        return a;
    for (int i = logn - 1; i >= 0; i--) {
        if (dp[a][i] != dp[b][i]) {
            a = dp[a][i];
            b = dp[b][i];
        }
    }
    return dp[a][0];
}