倍增

EricWan · 2024-08-18 10:28:28 · 题解

裸的基环树上倍增水题。

不难发现：输入的 X 相当于基环树上的父亲，我们直接倍增。

记录 anc_{i,j} 为 i 节点的 2^j 级祖先，可以得到 anc_{i,0}=X_i 和 anc_{i,j}=anc_{anc_{i,j-1},j-1}\ \forall\ i>0，这个和 LCA 一样、

对于每一个节点，还是倍增找答案。

因为 anc_{i,j} 可以 O(1) 计算，i\in[1,n] 而 j\in[0,\log_2K]，因此，本算法复杂度是 O(n\log K) 的。

之后就秒了。

#include <bits/stdc++.h>
#define int long long
#define MAXN 1000005
using namespace std;
int n, k, x[MAXN], anc[MAXN][61], a[MAXN];
signed main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        anc[i][0] = x[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= 60; i++)
        for (int j = 1; j <= n; j++)
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
    for (int i = 1; i <= n; i++) {
        int nowk = k, nowi = i;
        for (int j = 60; j >= 0; j--) {
            if (nowk >= (1ll << j)) {
                nowk -= (1ll << j);
                nowi = anc[nowi][j];
            }
        }
        cout << a[nowi] << " ";
    }
    return 0;
}