传送门
考虑维护每个颜色的虚树
按照 (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('
');
}
}
int main() {
int test;
In(test);
while (test) --test, Init(), Prework(), Solve();
return Flush(), 0;
}