|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||1024 MB||10||4||4||40.000%|
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.
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:
F F .. F[N - 2]
T T .. T[N - 2]
The sample judge will write a single line with the return value of
paths(N, K, F, T).
5 2 0 0 0 3 1 2 4 4
C++17, Java 8, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15, C++14 (Clang), C++17 (Clang), C++20 (Clang)