도시

어떤 먼 왕국에는 $0$부터 $N - 1$까지 번호가 붙은 $N$개의 도시가 있다. 도시들은 $N - 1$개의 양방향 도로로 연결되어 있다. 모든 도로의 길이는 같고, 각 도로는 정확히 두 도시를 연결하므로 임의의 두 도시 사이에는 유일한 경로가 존재한다.

두 도시 $A$와 $B$에 대해, $L(A, B)$를 도시 $A$와 $B$ 사이의 유일한 경로에 있는 도로의 개수라고 하자. 정수 $K$가 주어질 때, $L(A, B) = K$인 도시 쌍 $A, B$는 몇 개인가?

채점 프로그램은 다음 형식으로 입력을 읽는다.

• $1$번째 줄: N K
• $2$번째 줄: F[0] F[1] .. F[N - 2]
• $3$번째 줄: T[0] T[1] .. T[N - 2]

채점 프로그램은 paths(N, K, F, T)의 반환값을 한 줄에 출력한다.

• $1 \le K \le N \le 100\,000$