洛谷 P5903 【模板】树上 K 级祖先

// P5903【模板】树上 K 级祖先 —— 用倍增写（★ 而题面自己说了：这道题的正解不是它）
//
// ⚠⚠ 题目背景第一行就把话挑明了：
//     「**本题仅作为长链剖分求树上 k 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。**」
//   ⇒ 出题人想收的是 **O(1) 查询**的长链剖分（预处理 O(n log n)、每次询问 O(1)）。
//     倍增是 **O(log n) 查询** ⇒ `q` 到 5×10⁶ 时它慢一个 log。
//   ⇒ 这一页要回答的就是那句话的分量：**倍增在这道题上到底还剩多少余量**（解析页第 ③ 步）。
//
// ★ 而这道题真正会咬人的四处，一处都不在「怎么跳」上：
//   ① ⚠⚠ **询问是程序内生成的，而且强制在线** —— `x_i` 和 `k_i` 都要异或上 `ans_{i−1}`
//      ⇒ **不能离线排序**，也不能先把 q 个询问读进来。
//   ② ⚠⚠ **那个随机函数必须一字不差地照抄**：`ui` 是 **unsigned**，
//      三次移位是 `<<13 / >>17 / <<5`，而且 `get` 会**把 s 改掉**（`return s = x`）。
//   ③ ⚠ **根的深度是 1**（题面写死的）—— 因为 `k_i` 是对 `d[x_i]` 取模，
//      根的深度要是写成 0，那儿就是一次**除以零**。
//   ④ ⚠⚠ **输出要 `long long`**：`i × ans_i` 最大 5×10⁶ × 5×10⁵ = **2.5×10¹²**。
//
// ⚠⚠ 存法**不能**照搬 [P3379](/sol/p3379/) 那一页量出来的结论（解析页第 ③ 步量了）：
//   那道题求 LCA 要**把 20 层全比一遍** ⇒ `up[MAXN][LOG]`（同一个点的 20 层挨在一起）赢 10 倍；
//   而这道题只读 `k` 的那几个二进制位 —— 随机树上 `k ≤ 31` ⇒ **只碰得到最低 5 层**
//   ⇒ 反过来是 `up[LOG][MAXN]`（同一层的点挨在一起，只碰 10 MB）赢，端到端 0.77 vs 1.17 秒。
//   ⇒ ★★ 「换个存法快多少」的主语不是这张表，是**你会去读它的哪一部分**。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned int ui;

const int MAXN = 500005;
const int LOG = 20;

int up[LOG][MAXN];
int dep[MAXN];                    // ⚠ ③ 根的深度是 1
int fa[MAXN];
int n, root;
long long q;
ui s;

/** ⚠ ② 题面给的随机函数，一个字都不能改 */
inline ui getRnd(ui x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return s = x;
}

/* ---- 快读：输入只有 n + 3 个整数，可那也有 3.4 MB ---- */
static char ibuf[1 << 22];
static size_t ilen = 0, ipos = 0;
inline int gc() {
    if (ipos == ilen) { ilen = fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (!ilen) return -1; }
    return ibuf[ipos++];
}
inline long long readInt() {
    int c = gc();
    long long x = 0;
    while (c < '0' || c > '9') c = gc();
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

int main() {
    n = (int)readInt();
    q = readInt();
    s = (ui)readInt();
    vector<vector<int> > son(n + 1);
    for (int i = 1; i <= n; i++) {
        fa[i] = (int)readInt();
        if (fa[i] == 0) root = i;
        else son[fa[i]].push_back(i);
    }

    /* BFS 求 dep 和 up[·][0]（⚠ 父亲编号不保证更小，所以不能顺着 1..n 递推）*/
    {
        vector<int> que;
        que.reserve(n);
        dep[root] = 1;                       // ⚠ ③ 根的深度是 1
        up[0][root] = root;                  // 根的父亲设成它自己，跳过头就停在根
        que.push_back(root);
        for (size_t i = 0; i < que.size(); i++) {
            int u = que[i];
            for (size_t j = 0; j < son[u].size(); j++) {
                int v = son[u][j];
                dep[v] = dep[u] + 1;
                up[0][v] = u;
                que.push_back(v);
            }
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++)
            up[k][v] = up[k - 1][up[k - 1][v]];

    long long ans = 0;                       // ⚠ ④ i × ans_i 最大 2.5×10¹²
    ui last = 0;                             // ans_0 = 0
    for (long long i = 1; i <= q; i++) {
        int x = (int)(((getRnd(s) ^ last) % (ui)n) + 1);
        ui k = (getRnd(s) ^ last) % (ui)dep[x];
        int u = x;
        for (int b = 0; b < LOG; b++)        // 把 k 拆成二进制，该跳哪几位就跳哪几位
            if ((k >> b) & 1u) u = up[b][u];
        last = (ui)u;
        ans ^= i * (long long)u;
    }
    printf("%lld\n", ans);
    return 0;
}

// P5903 的两笔账：两条路各做多少次基本动作（机器无关），以及那张表的两种存法差多少
//
// 用法：./p5903Count <csv|table> [q] < 一份输入（q 不给就用输入里的）
//
// ★ 这道题的 `k_i` 是**对深度取模**摇出来的 ⇒ 平均要跳的步数直接由树的形状决定：
//   随机树深度只有 40 出头 ⇒ 平均爬 20 步；一条链就是平均爬 n/4 = 12.5 万步。
//   ⇒ 「一步一步爬」和「倍增」谁快，在这道题上**由数据说了算**。

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

typedef unsigned int ui;
static double nowMs() { struct timeval tv; gettimeofday(&tv, nullptr); return tv.tv_sec * 1000.0 + tv.tv_usec / 1000.0; }

const int MAXN = 500005;
const int LOG = 20;

static int upA[LOG][MAXN];                 // 正文那种存法
static int upB[MAXN][LOG];                 // 转置（[P3379](/sol/p3379/) 那一页量出来更快的那种）
static int dep[MAXN], fa[MAXN];
static int n, root;
static long long q;
static ui s;

static inline ui getRnd(ui x) { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return s = x; }

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d %lld %u", &n, &q, &s) != 3) return 0;
    if (argc > 2) q = atoll(argv[2]);
    ui s0 = s;

    vector<vector<int> > son(n + 1);
    for (int i = 1; i <= n; i++) {
        if (scanf("%d", &fa[i]) != 1) return 0;
        if (fa[i] == 0) root = i; else son[fa[i]].push_back(i);
    }
    {
        vector<int> que; que.reserve(n);
        dep[root] = 1; fa[root] = root; upA[0][root] = root; que.push_back(root);
        for (size_t i = 0; i < que.size(); i++) {
            int u = que[i];
            for (size_t j = 0; j < son[u].size(); j++) {
                int v = son[u][j];
                dep[v] = dep[u] + 1; upA[0][v] = u; que.push_back(v);
            }
        }
    }
    for (int k = 1; k < LOG; k++) for (int v = 1; v <= n; v++) upA[k][v] = upA[k - 1][upA[k - 1][v]];
    for (int v = 1; v <= n; v++) for (int k = 0; k < LOG; k++) upB[v][k] = upA[k][v];

    int maxDep = 0;
    for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);

    /* ① 机器无关：暴力要爬多少步、倍增要跳多少次（先把询问摇一遍，顺手数出来） */
    long long climb = 0, jumps = 0;
    {
        s = s0;
        ui last = 0;
        for (long long i = 1; i <= q; i++) {
            int x = (int)(((getRnd(s) ^ last) % (ui)n) + 1);
            ui k = (getRnd(s) ^ last) % (ui)dep[x];
            climb += k;
            jumps += __builtin_popcount(k);
            int u = x;
            for (int b = 0; b < LOG; b++) if ((k >> b) & 1u) u = upB[u][b];
            last = (ui)u;
        }
    }

    /* ② 三条路各跑一遍，只量查询那一段 */
    long long ansA = 0, ansB = 0, ansC = 0;
    double msA, msB, msC;
    {
        s = s0; ui last = 0; double t = nowMs();
        for (long long i = 1; i <= q; i++) {
            int x = (int)(((getRnd(s) ^ last) % (ui)n) + 1);
            ui k = (getRnd(s) ^ last) % (ui)dep[x];
            int u = x;
            for (int b = 0; b < LOG; b++) if ((k >> b) & 1u) u = upA[b][u];
            last = (ui)u; ansA ^= i * (long long)u;
        }
        msA = nowMs() - t;
    }
    {
        s = s0; ui last = 0; double t = nowMs();
        for (long long i = 1; i <= q; i++) {
            int x = (int)(((getRnd(s) ^ last) % (ui)n) + 1);
            ui k = (getRnd(s) ^ last) % (ui)dep[x];
            int u = x;
            for (int b = 0; b < LOG; b++) if ((k >> b) & 1u) u = upB[u][b];
            last = (ui)u; ansB ^= i * (long long)u;
        }
        msB = nowMs() - t;
    }
    if (climb <= 2000000000LL) {              // 爬得动才量，链上就别指望了
        s = s0; ui last = 0; double t = nowMs();
        for (long long i = 1; i <= q; i++) {
            int x = (int)(((getRnd(s) ^ last) % (ui)n) + 1);
            ui k = (getRnd(s) ^ last) % (ui)dep[x];
            int u = x;
            for (ui c = 0; c < k; c++) u = fa[u];
            last = (ui)u; ansC ^= i * (long long)u;
        }
        msC = nowMs() - t;
    } else { msC = -1; ansC = ansA; }

    char buf[64];
    vector<pair<string, string> > out;
    auto putD = [&](const string& k, double x, int p = 1) { snprintf(buf, sizeof(buf), "%.*f", p, x); out.push_back(make_pair(k, string(buf))); };
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("q", to_string(q)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("climb", to_string(climb)));
    out.push_back(make_pair("jumps", to_string(jumps)));
    out.push_back(make_pair("same", string((ansA == ansB && ansA == ansC) ? "1" : "0")));
    putD("ms_A", msA);
    putD("ms_B", msB);
    putD("ms_climb", msC);
    putD("ratio_AB", msB > 0 ? msA / msB : 0, 2);

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%s\n", out[i].first.c_str(), out[i].second.c_str());
    else for (size_t i = 0; i < out.size(); i++) printf("  %-10s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}