/*
线段树合并 维护每个颜色的最小深度即可
??? 要强制在线
考虑不限制深度的方法统计子树中的颜色个数将每种颜色按照dfs序排序, 然后树上每个点答案贡献 + 1, 同种颜色相邻dfs序的lca处-1
这样统计子树和即可
考虑假如有深度限制的话, 这个方法可以离线来做, 按照深度从小到大一层一层地加入点, 同时对于每种
颜色按照dfs序维护set, 那么对于所有的询问按照deep[x] + d排序就可以处理了
现在要求在线, 那么按照深度建立主席树, 每次在上面查询就好了
l 写成1 debug3小时
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#include<set>
#define ll long long
#define M 200010
#define mmp make_pair
using namespace std;
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
int n, m, t, deep[M], root[M], sz[M], son[M], fa[M], top[M], dfn[M], low[M], dft, cor[M], maxdeep, ans, cnt;
vector<int> to[M], note[M];
struct cmp {
bool operator () (const int &a, const int &b) const {
return dfn[a] < dfn[b];
}
};
set<int, cmp> st[M];
set<int>::iterator it, it2;
void init() {
for(int i = 1; i <= n; i++) vector<int>().swap(to[i]), vector<int>().swap(note[i]), st[i].clear(), son[i] = 0;
maxdeep = ans = cnt = dft = 0;
}
void dfs(int now, int f) {
deep[now] = deep[f] + 1;
// note[deep[now]].push_back(now);
maxdeep = max(maxdeep, deep[now]);
sz[now] = 1;
for(int i = 0; i < to[now].size(); i++) {
int vj = to[now][i];
dfs(vj, now);
if(sz[vj] > sz[son[now]]) son[now] = vj;
sz[now] += sz[vj];
}
}
void dfs(int now) {
dfn[now] = ++dft;
note[deep[now]].push_back(now);/*
if(son[now]) {
top[son[now]] = top[now];
dfs(son[now]);
}*/
for(int i = to[now].size() - 1; i >= 0; i--) {
int vj = to[now][i];
if(vj == son[now]) top[vj] = top[now];
else top[vj] = vj;
dfs(vj);
}
low[now] = dft;
}
int lca(int a, int b) {
while(top[a] != top[b]) {
if(deep[top[a]] < deep[top[b]]) swap(a, b);
a = fa[top[a]];
}
if(deep[a] > deep[b]) swap(a, b);
return a;
}
int rt[M], ls[M * 50], rs[M * 50], v[M * 50];
void insert(int l, int r, int &now, int pos, int val) {
if(!now) {
now = ++cnt;
ls[now] = rs[now] = v[now] = 0;
}
if(l == r) {
v[now] += val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) insert(l, mid, ls[now], pos, val);
else insert(mid + 1, r, rs[now], pos, val);
v[now] = v[ls[now]] + v[rs[now]];
}
int merge(int last, int now, int l, int r) {
if(!last || !now) return last + now;
if(l == r) {
v[now] += v[last];
return now;
}
int mid = (l + r) >> 1;
ls[now] = merge(ls[last], ls[now], l, mid);
rs[now] = merge(rs[last], rs[now], mid + 1, r);
v[now] = v[ls[now]] + v[rs[now]];
return now;
}
int query(int l, int r, int now, int ln, int rn) {
if(l > rn || r < ln) return 0;
if(l >= ln && r <= rn) return v[now];
int mid = (l + r) >> 1;
return query(l, mid, ls[now], ln, rn) + query(mid + 1, r, rs[now], ln, rn);
}
int main() {
// freopen("1.in", "r", stdin); freopen("2.out", "w", stdout);
t = read();
while(t--) {
n = read(), m = read();
init();
for(int i = 1; i <= n; i++) cor[i] = read();
for(int i = 2; i <= n; i++) fa[i] = read(), to[fa[i]].push_back(i);
dfs(1, 0);
top[1] = 1;
dfs(1);
rt[0] = 0;
for(int d = 1; d <= maxdeep; d++) {
rt[d] = 0;
for(int i = note[d].size() - 1; i >= 0; i--) {
int x = note[d][i];
// cout << x << " " << deep[x] << " " << dfn[x] << " " << cnt<< "\n";
insert(1, n, rt[d], dfn[x], 1);
it = st[cor[x]].lower_bound(x);
int pre = -1, nxt = -1;
if(it != st[cor[x]].end()) nxt = *it;
if(it != st[cor[x]].begin()) pre = *(--it);
if(pre != -1) insert(1, n, rt[d], dfn[lca(pre, x)], -1);
if(nxt != -1) insert(1, n, rt[d], dfn[lca(x, nxt)], -1);
if(pre != -1 && nxt != -1) insert(1, n, rt[d], dfn[lca(pre, nxt)], 1);
st[cor[x]].insert(x);
}
rt[d] = merge(rt[d - 1], rt[d], 1, n);
}
// for(int i = 1; i < n; i++) cout << lca(i, i + 1) << " ";
// break;
while(m--) {
int x = read() ^ ans, d = read() ^ ans;
d = min(maxdeep, deep[x] + d);
ans = query(1, n, rt[d], dfn[x], low[x]);
cout << ans << '\n';
}
}
return 0;
}
/*
3
3 3
1 2 3
1 2
1 1
2 2
3 3
5 8
1 3 3 2 2
1 1 3 3
1 0
0 0
3 0
1 3
2 1
2 0
6 2
4 1
5 8
1 3 3 2 2
1 1 3 3
1 0
0 0
3 0
1 3
2 1
2 0
6 2
4 1
1
5 5
1 2 3 4 5
1 1 1 1
1 1
1 1
0 0
1 1
5 5
*/
转载于:https://www.cnblogs.com/luoyibujue/p/10518344.html
