21334번 - Cities 다국어언어 제한함수 구현

문제

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$?

예제

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

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. Your task is to compute how many pairs of cities have exactly $K$ roads between them. You will implement the function paths(N, K, F, T).

• paths(N, K, F, T) - this function will be called exactly once by the judge.
  • N: the number of cities in the kingdom.
  • K: the number of roads between pairs of cities we are interested in.
  • F: an array with $N - 1$ elements. F[i] (0ドル \le i < N$) contains one of the cities that the $i$:th road connects.
  • T: an array with $N - 1$ elements. T[i] (0ドル \le i < N$) contains the other city that the $i$:th road connects.
  • It is always possible to travel between any pair of cities using the roads.
  • The function should return the number of pairs of cities that has exactly $K$ roads between them.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at attachments.zip.

입력

The sample judge reads input in the following format:

• line 1ドル$: N K
• line 2ドル$: F[0] F[1] .. F[N - 2]
• line 3ドル$: T[0] T[1] .. T[N - 2]

출력

The sample judge will write a single line with the return value of paths(N, K, F, T).

제한

• 1ドル \le K \le N \le 100,000円$

힌트