题解：P4810 [COCI 2014/2015 #3] STOGOVI

Forgetfulness · 2025-10-05 11:02:06 · 题解

校内 T4，打了个神秘树剖跑路了。

主要思路都是一样的，维护每一个版本的栈顶 top_i，那么分别对于每个操作进行一些修改。

• a 操作，直接将 top_i = i；
• b 操作，相当于要询问父亲的父亲的栈顶，也就是 fa_{top_v}，删掉了 top_v。
• c 操作，相当于不做任何操作，top_i = top_v，答案就是 lca 的深度，dep_{LCA(top_v, top_w)}。

Q：为什么用栈顶元素做这些操作？\\ A：由于删除操作的存在。如果直接用编号的话，可能就把删除忽略掉，导致答案错误。

Q：为什么只在加元素时维护这些数组？\\ A：不难发现，每一个版本的栈顶元素 top_i 都是在一次 a 操作后被加进来的，所以每一个节点都可以回溯到一个最近的 a 操作。而我们关联答案也只需要 top_i，所以我们只需维护 a 操作的数组即可。

如果你想，你也可以对于每个操作维护一次。

主要思路就这样，实现方式有很多种，这里只给最简单的倍增不建图了。

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

const int N = 3e5 + 5, M = 20 + 5;
int n, top[N], dep[N], fa[N][M], lg[N];

int lca (int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    while (dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y) return x;

    for (int i = lg[dep[x]] - 1; i >= 0; --i)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int main () {

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i);
    for (int i = 1; i <= n; ++i) {
        char opt; int v;
        cin >> opt >> v;
        if (opt == 'a') {
            // 直接在加元素的时候维护 
            dep[i] = dep[top[v]] + 1;
            top[i] = i;
            fa[i][0] = top[v];
            for (int j = 1; j <= 19; ++j) fa[i][j] = fa[fa[i][j - 1]][j - 1];
        } else if (opt == 'b') {
            top[i] = fa[top[v]][0];
            cout << top[v] << '\n';
        } else {
            int w;
            cin >> w;
            top[i] = top[v];
            cout << dep[lca (top[v], top[w])] << '\n';
        }
    }

    return 0;
}