可以类比序列上的数颜色，在同一棵子树内把每种颜色的贡献放在最浅的深度上。
考虑怎么维护。
首先维护一棵权值线段树，代表每个深度所具有的颜色数（如上所述，贡献在最浅深度上）。
但是合并的时候如何更新呢？
考虑再来一棵权值线段树，维护每个颜色的最浅深度，然后在合并的时候更新另一棵。
然后强制在线就可持久化第一棵权值线段树。
然鹅，\(500\) 组数据把我的常数卡成狗……
几乎跑了一分钟的样子……
此代码无法在 BZOJ 上通过。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w ? x = -x : x;
}
const int N = 1e5;
int T,n,m;
int a[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
int edge_tot;
inline void add(int u,int v)
{
to[++edge_tot] = v,pre[edge_tot] = first[u],first[u] = edge_tot;
}
struct node
{
int val;
int ls,rs;
} seg[2][(N << 6) + 10];
int tot[2];
int rt[2][N + 5];
inline void insert1(int x,int k,int &p,int tl,int tr)
{
!p ? (p = ++tot[0],seg[0][p].val = 0x3f3f3f3f) : 0;
seg[0][p].val = min(seg[0][p].val,k);
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert1(x,k,seg[0][p].ls,tl,mid) : insert1(x,k,seg[0][p].rs,mid + 1,tr);
}
inline void insert2(int x,int k,int &p,int tl,int tr)
{
seg[1][++tot[1]] = seg[1][p],p = tot[1],seg[1][p].val += k;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert2(x,k,seg[1][p].ls,tl,mid) : insert2(x,k,seg[1][p].rs,mid + 1,tr);
}
inline int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[1][p].val;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid ? ret += query(l,r,seg[1][p].ls,tl,mid) : 0;
r > mid ? ret += query(l,r,seg[1][p].rs,mid + 1,tr) : 0;
return ret;
}
inline int merge1(int x,int y,int &rt)
{
if(!x || !y)
return x | y;
seg[0][x].val = min(seg[0][x].val,seg[0][y].val);
if(!seg[0][x].ls && !seg[0][x].rs && !seg[0][y].ls && !seg[0][y].rs)
insert2(max(seg[0][x].val,seg[0][y].val),-1,rt,1,n);
else
seg[0][x].ls = merge1(seg[0][x].ls,seg[0][y].ls,rt),seg[0][x].rs = merge1(seg[0][x].rs,seg[0][y].rs,rt);
return x;
}
inline int merge2(int x,int y)
{
if(!x || !y)
return x | y;
int p = ++tot[1];
seg[1][p].val = seg[1][x].val + seg[1][y].val;
seg[1][p].ls = merge2(seg[1][x].ls,seg[1][y].ls),seg[1][p].rs = merge2(seg[1][x].rs,seg[1][y].rs);
return p;
}
int fa[N + 5],dep[N + 5];
inline void dfs(int p)
{
insert1(a[p],dep[p],rt[0][p],1,n);
insert2(dep[p],1,rt[1][p],1,n);
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs(to[i]),rt[0][p] = merge1(rt[0][p],rt[0][to[i]],rt[1][p]),rt[1][p] = merge2(rt[1][p],rt[1][to[i]]);
}
int lastans;
int main()
{
read(T);
while(T--)
{
memset(first,0,sizeof first);
memset(rt,0,sizeof rt);
memset(seg,0,sizeof seg);
lastans = edge_tot = tot[0] = tot[1] = 0;
seg[0][0].val = 0x3f3f3f3f;
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(a[i]);
int u;
for(register int i = 2;i <= n;++i)
read(u),add(u,i);
dep[1] = 1,fa[1] = 0,dfs(1);
int x,d;
while(m--)
{
read(x),read(d),x ^= lastans,d ^= lastans;
printf("%d\n",lastans = query(dep[x],min(dep[x] + d,n),rt[1][x],1,n));
}
}
}