BZOJ4771: 七彩树

传送门
考虑维护每个颜色的虚树
按照 \(dfn\) 顺序维护这些点，在这些点上 \(+1\)，相邻点的 \(lca\) 处 \(-1\)，这样，无论包含哪一个子树的几个点，子树权值和始终为 \(1\)
可以用 \(set+LCA\) 实现
现在变成了二维数点的问题，按照深度依次加入每个点用主席树维护，每个线段树维护 \(dfs\) 序即可

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

namespace IO {
    const int maxn(1 << 21 | 1);

    char ibuf[maxn], obuf[maxn], *iS, *iT, *oS = obuf, *oT = obuf + maxn - 1, c, st[66];
    int tp, f;

    inline char Getc() {
        return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++)) : *iS++;
    }

    template <class Int> inline void In(Int &x) {
        for (f = 1, c = Getc(); c < '0' || c > '9'; c = Getc()) f = c == '-' ? -1 : 1;
        for (x = 0; c >= '0' && c <= '9'; c = Getc()) x = (x << 1) + (x << 3) + (c ^ 48);
        x *= f;
    }

    inline void Flush() {
        fwrite(obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }

    inline void Putc(char c) {
        *oS++ = c;
        if (oS == oT) Flush();
    }

    template <class Int> void Out(Int x) {
        if (!x) Putc('0');
        if (x < 0) Putc('-'), x = -x;
        while (x) st[++tp] = x % 10 + '0', x /= 10;
        while (tp) Putc(st[tp--]);
    }
}

using IO :: In;
using IO :: Out;
using IO :: Putc;
using IO :: Flush;

const int maxn(1e5 + 5);

int n, m, first[maxn], tot, rt[maxn], deep[maxn], col[maxn], ed[maxn];
int son[maxn], size[maxn], top[maxn], fa[maxn], nxt[maxn], dfn[maxn], mxd;
int ls[maxn * 80], rs[maxn * 80], sz[maxn * 80], idx, pos[maxn], id[maxn];
set <int> st[maxn];
set <int> :: iterator it, ot;

inline void Init() {
    int i;
    while (tot) ls[tot] = rs[tot] = sz[tot] = 0, --tot;
    memset(rt, 0, sizeof(rt)), memset(first, 0, sizeof(first));
    In(n), In(m), idx = mxd = 0;
    for (i = 1; i <= n; ++i) In(col[i]), id[i] = i, st[i].clear();
    for (i = 2; i <= n; ++i) In(fa[i]), nxt[i] = first[fa[i]], first[fa[i]] = i;
}

void Dfs1(int u) {
    int v;
    size[u] = 1, son[u] = 0, mxd = max(mxd, deep[u]);
    for (v = first[u]; v; v = nxt[v]) {
        deep[v] = deep[u] + 1, Dfs1(v);
        size[u] += size[v];
        son[u] = size[v] > size[son[u]] ? v : son[u];
    }
}

void Dfs2(int u, int tp) {
    int v;
    dfn[u] = ++idx, pos[idx] = u, top[u] = tp;
    if (son[u]) Dfs2(son[u], tp);
    for (v = first[u]; v; v = nxt[v]) if (v ^ son[u]) Dfs2(v, v);
    ed[u] = idx;
}

inline int Cmp(int x, int y) {
    return deep[x] < deep[y];
}

void Modify(int &x, int l, int r, int p, int v) {
    ls[++tot] = ls[x], rs[tot] = rs[x], sz[tot] = sz[x] + v, x = tot;
    if (l == r) return;
    int mid = (l + r) >> 1;
    p <= mid ? Modify(ls[x], l, mid, p, v) : Modify(rs[x], mid + 1, r, p, v);
}

int Query(int x, int y, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return sz[x] - sz[y];
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid) ret = Query(ls[x], ls[y], l, mid, ql, qr);
    if (qr > mid) ret += Query(rs[x], rs[y], mid + 1, r, ql, qr);
    return ret;
}

inline int LCA(int x, int y) {
    assert(x && y);
    while (top[x] ^ top[y]) deep[top[x]] > deep[top[y]] ? x = fa[top[x]]: y = fa[top[y]];
    return deep[x] < deep[y] ? x : y;
}

inline void Prework() {
    int i, j, c, lst = 0, p;
    deep[1] = 1, Dfs1(1), Dfs2(1, 1), sort(id + 1, id + n + 1, Cmp);
    for (i = 1; i <= n; ++i) {
        c = col[p = id[i]];
        while (lst < deep[p]) rt[lst + 1] = rt[lst], ++lst;
        Modify(rt[lst], 1, n, dfn[p], 1);
        it = ot = st[c].insert(dfn[p]).first, ++ot;
        if (it != st[c].begin()) --it, Modify(rt[lst], 1, n, dfn[LCA(pos[*it], p)], -1), ++it;
        if (ot != st[c].end()) Modify(rt[lst], 1, n, dfn[LCA(pos[*ot], p)], -1);
        if (it != st[c].begin() && ot != st[c].end()) --it, Modify(rt[lst], 1, n, dfn[LCA(pos[*it], pos[*ot])], 1), ++it;
    }
}

inline void Solve() {
    int i, u, x, y, ans = 0;
    for (i = 1; i <= m; ++i) {
        In(u), In(y), u ^= ans, y ^= ans;
        x = deep[u], y = min(mxd, x + y);
        if (x > y) Putc('0'), ans = 0;
        else Out(ans = Query(rt[y], rt[x - 1], 1, n, dfn[u], ed[u]));
        Putc('\n');
    }
}

int main() {
    int test;
    In(test);
    while (test) --test, Init(), Prework(), Solve();
    return Flush(), 0;
}

BZOJ4771: 七彩树

原文：https://www.cnblogs.com/cjoieryl/p/10275659.html