【題解】CSES 1688 Company Queries II

【題目敘述】https://cses.fi/problemset/task/1688/

#include <iostream>
using namespace std;
 
int n, q, a, b, p[200005][20], d[200005];
 
int dp(int x){
    if (d[x]) return d[x];
    if (x == 1) return d[x] = 1;
    return d[x] = dp(p[x][0])+1;
}
int solve(int a, int b){
    int x = dp(a), y = dp(b);
    if (x > y){
        swap(a, b);
        swap(x, y);
    }
    y -= x;
    for (int i = 0; i < 20; i++){
        if (y & (1<<i)) b = p[b][i];
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--){
        if (p[a][i] != p[b][i]){
            a = p[a][i];
            b = p[b][i];
        }
    }
    return p[a][0];
}
 
int main() {
    cin >> n >> q;
    for (int i = 2; i <= n; i++){
        cin >> p[i][0];
    }
    for (int i = 1; i < 20; i++){
        for (int j = 1; j <= n; j++){
            p[j][i] = p[p[j][i-1]][i-1];
        }
    }
    while (q--){
        cin >> a >> b;
        cout << solve(a, b) << "\n";
    }
}
分享本文 Share with friends