2017-09-29 03:22

Claris Loves Painting

  • as
  • color
  • it
  • lines
  • each

Problem Description
Claris loves painting very much, so he painted a tree with beautiful colors.

The tree is a rooted tree with n nodes which are conveniently labeled by 1,2,...,n. Its root is the 1-st node, and the i-th node is painted with color ci. If ci=cj, then we think these two nodes have the same color.

We define depthi as the distance between the i-th node and the root, and simply, the distance between two adjacent nodes is always 1.

Standing in front of this beautiful tree, Claris comes up with m questions.
In each question, there are two integers x and d, which means that Claris wants to know the number of different kinds of colors occur in S, where S={v|v in x′s subtree and depthv≤depthx+d}.

The first line of the input contains an integer T(1≤T≤500), denoting the number of test cases.

In every test case, there are two integers n(1≤n≤100000) and m(1≤m≤100000) in the first line, denoting the number of nodes and queries.
The second line contains n integers, the i-th integer ci(1≤ci≤n) denotes the color of the i-th node.
The third line contains n−1 integers, the i-th integer fi+1(1≤fi<i) denotes the father of the i+1-th node.
In the following m lines, each line contains two integers x(1≤x≤n) and d(0≤d<n), denoting each query.

The input has been encoded, if you read x and d, the real x and d are x⊕last and d⊕last, where last is the answer of the previous query and ⊕ means bitwise exclusive-or.

Notice :
If it is the first query in this test case, then last=0.
It is guaranteed that ∑n≤500000 and ∑m≤500000.

For each query output a single integer in a line, denoting the answer.

Sample Input
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

Sample Output

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享