33OJ
登录 注册

#P17814. [ICPC 2019 Nanchang R] Tree

[ICPC 2019 Nanchang R] Tree

Problem Description

Consider a rooted tree consisting of nn vertices where the first vertex is the root. The ii-th vertex is endowed with the value viv_i.

Now you are given a positive integer kk. An ordered pair of vertices (x,y)(x,y), indicating the xx-th and the yy-th vertices in the tree, is valid if it satisfies the following conditions:

  • x≠yx\neq y;
  • The xx-th vertex is not an ancestor of the yy-th one;
  • The yy-th vertex is not an ancestor of the xx-th one;
  • The length of the shortest path connection these two vertices is up to kk;
  • Take the value of the lowest common ancestor of these two vertices, denoted by vzv_z. Then vx+vy=2vzv_x+v_y=2v_z.

Can you calculate the total number of valid pairs of vertices in this tree?

Input Format

The first line contains two integers nn and k (1≤n,k≤105)k~(1 \le n, k \le 10^5) which is described as above.

The second line contains nn integers, the ii-th of which is the value of the ii-th vertex viv_i (0≤vi≤n0 \le v_i \le n).

The third line contains n−1n-1 integers, the ii-th of which represents the index of the parent vertex of the (i+1)(i+1)-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 (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) are regarded as the same if x1=x2x_1=x_2 and y1=y2y_1=y_2.

3 2
1 2 3
1 1
0
3 1
2 1 3
1 1
0
3 2
2 1 3
1 1
2