SOLVE
LATER
Monk has become a master in graph and trees, so he is ready with a task for you.
Given a Tree T consisting of N nodes rooted at node 1, each node has a value, where the value of the \(i^{th}\) node is \(A[i]\).
In addition to the tree, you have also been given an integer K. Now, you need to find in this tree, the number of distinct pairs \((i,j)\) where node i is an ancestor of node j, and the XOR of the values of all nodes lying on the path from i to j is equal to K.
In short, you need to find the number of pairs \((i,j)\), where node i is an ancestor of j,
and :\( \forall x\) lying on the path from i to j inclusive, \(\oplus A[x]\) = K.
Here, the \(\oplus\) symbol denotes the logical XOR operation.
Note:
A node x is considered an ancestor of another node y if x is parent of y or x is an ancestor of parent of y. For the purposes of this problem, we consider every node to be an ancestor of itself.
Can you do it ?
Input Format :
The first line contains 2 space separated integers N and K. The next line contains N space separated integers. where the \(i^{th}\) integer denotes \(A[i]\).
The next line contains \(N-1\) space separated integers, where the \(i^{th}\) integer denotes the parent of node \(i+1\).
Output Format :
Print the required answer on a single line.
Constraints :
\( 1 \le N \le 10^5 \)
\( 0 \le K, A[i] \le 2^{20} \)
\( 1 \le parent[i] < i\), where \(2 \le i \le N\)
Here, the numbers written on the nodes represent their value, and the numbers written beside each node represents their index.
The pairs forming part of the answer are :
\((1,3)\) = \( 1 \oplus 2 \oplus 4=7\)
\((1,4)\) = \( 1 \oplus 2 \oplus 4=7\)
\((1,6)\) = \( 1 \oplus 2 \oplus 4=7\)