长链剖分入门

模拟赛考到了，但是完全不会。

填个坑。

P5903 【模板】树上 \(k\) 级祖先

#include <bits/stdc++.h>
#define emp emplace_back
using namespace std;
const int N = 5e5 + 5;
using ui = unsigned int;
using LL = long long;

int IO_flg = 0;
int _debug = 1;
class DEBUG {
public:
    inline void IOS() { if(!IO_flg) IO_flg = 1, ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); }
	inline void shift(int x) { _debug = x; }
    inline void read() {}
    inline void write() {}
#define TMP template <typename T>
#define TEMPA template <typename T, typename ...A>
    TMP inline void writeln(T x) { cout << x << endl; }
    TEMPA inline void read(T &x, A&...k) {
		if(!_debug) return;
        cin >> x, read(k...);
    }
    TEMPA inline void write(T x, A ...k) {
		if(!_debug) return;
        cout << x, write(k...);
    }
    TEMPA inline void writeln(T x, A ...k) {
		if(!_debug) return;
        cout << x << ' ', writeln(k...);
    }
    TMP inline void debug(T *arr, int M) {
		if(!_debug) return;
        for(int i = 1; i <= M; ++i) cout << arr[i] << ' ';
        cout << endl;
    }
	TMP inline void debug(vector <T> &arr) {
		if(!_debug) return;
		for(auto x : arr) cout << x << ' ';
		cout << endl;
	}
    TMP inline void debug(set <T> &arr) {
        if(!_debug) return;
        for(auto x : arr) cout << x << ' ';
        cout << endl;
    }
    TMP inline void debug(multiset <T> &arr) {
        for(auto x : arr) cout << x << ' ';
        cout << endl;
    }
    TMP inline void debug(T x) {
		if(!_debug) return;
        cout << "*" << x << endl;
    }
	TEMPA inline void debug(T x, A ...k) {
		if(!_debug) return;
		cout << "*" << x << ' ', debug(k...);
	}
    inline void file(const char *I = "in.txt", const char *O = "Ans.txt") {
        freopen(I, "r", stdin), freopen(O, "w", stdout);
    }
    inline void Exit() {
        if(!_debug) return;
        exit(0);
    }
    inline void judge(bool Exp) {
        if(!_debug) return;
        if(!Exp) 
            puts("Expression False!"), exit(0);
        puts("Expression True.");
    }
}D;

int n, q, S, rt;
int g[N], d[N], f[N][23], son[N], dep[N], top[N], ans;
// g[i] = log2(i), d[x] = depth of node x, dep[x] = length of chains
// son[x], top[x]
vector <int> Link[N], up[N], dw[N];
// up, dw: the node you get with skipping on the Long chain up and down
LL Ans;

inline ui gen(ui x) {
    return x ^= x << 13, x ^= x >> 17, x ^= x << 5, S = x;
}

void dfs(int x) {
    dep[x] = d[x] = d[f[x][0]] + 1;
    for(auto y : Link[x]) {
        f[y][0] = x;
        for(int i(0); f[y][i]; ++i) f[y][i + 1] = f[f[y][i]][i]; // f[i][j] = fa^(2^j)[i]
       dfs(y);
        if(dep[y] > dep[x]) dep[x] = dep[y], son[x] = y;
    }
}

void dfs(int x, int p) { // p = top of the chain
    top[x] = p;
    if(x == p) {
        for(int i = 0, now = x; i <= dep[x] - d[x]; ++i) 
            up[x].emp(now), now = f[now][0]; // go up
        for(int i = 0, now = x; i <= dep[x] - d[x]; ++i) 
            dw[x].emp(now), now = son[now]; // go down
    }
    if(son[x]) dfs(son[x], p);
    for(auto y : Link[x]) if(y != son[x]) dfs(y, y);
}

inline int ask(int x, int k) {
    if(!k) return x;
    x = f[x][g[k]], k -= 1 << g[k], k -= d[x] - d[top[x]], x = top[x];
	// first skip 2^g[k] steps, then skip to the top of the current chain
    return k >= 0 ? up[x][k] : dw[x][-k];
}

signed main() {
    D.file("in.txt", "Ans.txt");
    scanf("%d %d %d", &n, &q, &S), g[0] = -1;
    for(int i = 1; i <= n; ++i) 
        scanf("%d", &f[i][0]), Link[f[i][0]].emp(i), g[i] = g[i >> 1] + 1;
    rt = Link[0][0], dfs(rt), dfs(rt, rt);
    for(int i = 1, x, k; i <= q; ++i) {
        x = (gen(S) ^ ans) % n + 1, k = (gen(S) ^ ans) % d[x];
        Ans xor_eq 1LL * i * (ans = ask(x, k));
    }
    printf("%lld", Ans);
    return 0;
}