영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
In a far away kingdom, there are N cities numbered between 0 and N - 1. The cities are connected by N - 1 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 (1 ≤ K ≤ N ≤ 100000), described in the statement.
The two lines contains the N - 1 integers f_1, …, f_{N-1} (0 ≤ f_i < N) and the N - 1 integers t_1, …, t_{N-1} (0 ≤ t_i < N) respectively. These describe the roads of the city: there is a road between city f_i and t_i 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 | N ≤ 100 |
| 2 | 19 | N ≤ 1000 |
| 3 | 34 | K ≤ 10 |
| 4 | 38 | No additional constrsaints. |
Explanation of sample 1
Let the kingdom have N = 5 cities, connected by roads as in the figure below:
(그림은 원문 저장소에서 볼 수 있습니다)
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.
예제
예제 1
5 2 0 0 0 3 1 2 4 4
4