Hide

Problem R
Cities

Languages en sv

In a far away kingdom, there are N cities numbered between 0 and N1. The cities are connected by N1 two-way roads. Each road has the same length, and connects exactly two cities, such that there is a unique path between any pair of cities.

For any two cities A and B, denote by L(A,B) the number of roads of this unique path between cities A and B. Given an integer K, for how many pairs of cities A,B is L(A,B)=K?

Input

The first line contains the integers N and K (1KN100000), described in the statement.

The two lines contains the N1 integers f1,,fN1 (0fi<N) and the N1 integers t1,,tN1 (0ti<N) respectively. These describe the roads of the city: there is a road between city fi and ti for each i.

Output

Output the number of pairs of cities that have exactly K roads between them.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Group

Points

Constraints

1

9

N100

2

19

N1000

3

34

K10

4

38

No additional constrsaints.

Explanation of sample 1

Let the kingdom have N=5 cities, connected by roads as in the figure below:

\includegraphics[width=0.3\textwidth ]{sample.png}
Figure 1: Illustration of the example

The following 4 pairs have a single road between them: (0,1),(0,2),(0,4),(3,4).

The following 4 pairs have two roads between them: (0,3),(1,2),(1,4),(2,4).

The following 2 pairs have three roads between them: (1,3),(2,3).

This means that if for K=1,2,3, the answers would be 4,4,2 respectively.

Sample Input 1 Sample Output 1
5 2
0 0 0 3
1 2 4 4
4
Hide

Please log in to submit a solution to this problem

Log in