(Sky OJ) 145. Day 3 PG. 卦長的背包 [LCA]

https://pc2.tfcis.org/sky/index.php/problem/view/145/

LCA

#include <iostream>
#include <stdio.h>
#include <cassert>
#include <queue>
using namespace std;

typedef long long LL;
const int MAX_N = 2e5 + 6;
const int MAX_P = 19;

vector<int> edg[MAX_N];
int depth[MAX_N];
int p[MAX_N];
int lca[MAX_P][MAX_N];
int pin[MAX_N],pout[MAX_N];
int stamp;

void dfs(int id,int p,int cur_depth) {
    lca[0][id] = p;
    depth[id] = cur_depth;
    pin[id] = stamp++;
    for (int i:edg[id]) dfs(i,id,cur_depth+1);
    pout[id] = stamp++;
}

bool is_anc(int parent,int son ){
    return pin[parent] <= pin[son] && pout[son] <= pout[parent];
}

int query(int a,int b) {
    if (depth[a] > depth[b]) swap(a,b);
    if (is_anc(a,b)) return depth[b] - depth[a];
    int bb=b;
    for (int i=MAX_P-1;i>=0;i--) {
        if (!is_anc(lca[i][b],a)) b=lca[i][b];
    }
    b=lca[0][b];
    swap(b,bb);
    return depth[a] + depth[b] - depth[bb]*2;
}

int main () {
    int n;
    scanf("%d",&n);
    for (int i=2;n>=i;i++) {
        int p;
        scanf("%d",&p);
        edg[p].push_back(i);
    }
    stamp=0;
    dfs(1,1,1);
    for (int i=1;MAX_P>i;i++) {
        for (int j=1;n>=j;j++) {
            lca[i][j] = lca[i-1][lca[i-1][j]];
        }
    }
    queue<int> que;
    int last=1;
    que.push(1);
    LL ans=0;
    while (!que.empty()) {
        int t=que.front();
        que.pop();
        ans += query(last,t);
        last=t;
        for (int i:edg[t]) que.push(i);
    }
    printf("%lld\n",ans);
}