P4116 Qtree3 题解

Statax · 2025-12-16 13:07:53 · 题解

前置知识：分块思想、树剖。

我有一个不用 set、不用数据结构的唐方法。

题解

先把树的重链剖出来。

充分发扬人类智慧，在树剖时如果当前重链长度 \ge \sqrt{n} 我们就断开，下面重新作为重链开头。

然后就可以暴力做了。

具体的，修改操作暴力的从当前节点 x 跳到所在链的底部，根据 x 的颜色更新路上每个点的 cnt，这里 cnt 表示从链顶到该节点有多少个黑点。

查询操作我们就一直往上不断跳链到根，不断更新最靠近根的链，最后在这条链上暴力跳找答案。

注意事项、坑点

不可以只维护一条链上有没有黑点，可以自己简单证一下。

代码

时间复杂度大概是 O(能过)，修改是 O(\sqrt{n})，查询应该是 O(\sqrt{n}\log n)。

:::info[代码]

namespace SPT {
    int fa[MAXN], dep[MAXN], sz[MAXN];
    int son[MAXN], top[MAXN], button[MAXN];
    void dfs1 (int u, int f) {
        fa[u] = f;
        dep[u] = dep[f] + 1;
        sz[u] = 1;
        for (auto v : g[u]) {
            if (v == f) continue;
            dfs1 (v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
    }

    void dfs2 (int u, int tp, int len) {
        top[u] = tp, button[tp] = u;
        if (son[u]) {
            if (len == blk) {
                dfs2 (son[u], son[u], 1);
            } else {
                dfs2 (son[u], tp, len + 1);
            }
        }
        for (auto v : g[u]) {
            if (v != son[u] && v != fa[u]) {
                dfs2 (v, v, 1);
            }
        }
    }
} using namespace SPT;

void U (int x) {
    int sgn = (col[x] ? -1 : 1);
    for (int cur = button[top[x]]; cur != fa[x]; cur = fa[cur])
        cnt[cur] += sgn;
    col[x] ^= 1;
}

int Q (int x) {
    int T = -1, ret = -1;
    for (int cur = x; cur; cur = fa[top[cur]]) {
        if (cnt[cur]) {
            T = cur;
        }
    }
    if (T == -1) {
        return -1;
    }
    for (int cur = T; cur != fa[top[T]]; cur = fa[cur]) {
        if (col[cur]) {
            ret = cur;
        }
    }
    return ret;
}

signed main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> q;
    blk = sqrt (n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].eb (v);
        g[v].eb (u);
    }   
    dfs1 (1, 0);
    dfs2 (1, 1, 1);
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 0) {
            U (x);
        } else {
            cout << Q (x) << '\n';
        }
    }
    return 0;
}

:::