#P17814. [ICPC 2019 Nanchang R] Tree
[ICPC 2019 Nanchang R] Tree
Problem Description
Consider a rooted tree consisting of vertices where the first vertex is the root. The -th vertex is endowed with the value .
Now you are given a positive integer . An ordered pair of vertices , indicating the -th and the -th vertices in the tree, is valid if it satisfies the following conditions:
- ;
- The -th vertex is not an ancestor of the -th one;
- The -th vertex is not an ancestor of the -th one;
- The length of the shortest path connection these two vertices is up to ;
- Take the value of the lowest common ancestor of these two vertices, denoted by . Then .
Can you calculate the total number of valid pairs of vertices in this tree?
Input Format
The first line contains two integers and which is described as above.
The second line contains integers, the -th of which is the value of the -th vertex ().
The third line contains integers, the -th of which represents the index of the parent vertex of the -th vertex.
We guarantee that the given tree is indeed a tree.
Output Format
Output the number of valid pairs of vertices in a line.
Two pairs and are regarded as the same if and .
3 2
1 2 3
1 1
0
3 1
2 1 3
1 1
0
3 2
2 1 3
1 1
2