阅读程序（第二题）：树上倍增求 LCA

阅读下面程序，完成后面的判断题和单选题。判断题正确填 A，错误填 B。

树的输入格式为：第一行两个整数 n, q；第二行 n−1 个整数，依次表示结点 2 到结点 n 的父结点编号（保证父结点编号小于该结点编号，结点 1 为根）；接下来 q 行，每行两个整数 u, v。以下各题若无特别说明，均以输入

9 8
1 1 2 2 3 3 5 5
4 5
8 9
6 7
8 6
9 3
4 8
5 8
6 2

为例。

#include <algorithm>
#include <cstdio>
#include <cstring>

const int MAXN = 100005;
const int LOG = 17;

int n, q;
int head[MAXN], nxt[MAXN], to[MAXN], tot;
int dep[MAXN], up[MAXN][LOG + 1];

void add(int u, int v) {
    nxt[++tot] = head[u];
    to[tot] = v;
    head[u] = tot;
}

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    up[u][0] = fa;
    for (int j = 1; j <= LOG; ++j)
        up[u][j] = up[up[u][j - 1]][j - 1];
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (v != fa) dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    for (int j = LOG; j >= 0; --j)
        if (dep[u] - (1 << j) >= dep[v])
            u = up[u][j];
    if (u == v) return u;
    for (int j = LOG; j >= 0; --j)
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    return up[u][0];
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 2; i <= n; ++i) {
        int p;
        scanf("%d", &p);
        add(p, i);
        add(i, p);
    }
    dfs(1, 0);
    long long s = 0;
    for (int i = 1; i <= q; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int w = lca(u, v);
        printf("%d\n", w);
        s += w;
    }
    printf("%lld\n", s);
    return 0;
}