Cities

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree with N nodes, count the unordered pairs of cities whose unique path contains exactly K edges.

Level: Medium7 of 10
Topics: Tree, DFS, Divide and conquer, Prefix sum
Solved: No attempts yet

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, so there is a unique path between any pair of cities.

For any two cities $A$ and $B$ , let $L(A, B)$ be the number of roads on the 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 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]

Output

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

Constraints

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

Examples1

Example 1
Input
```
5 2
0 0 0 3
1 2 4 4
```
Expected output
```
4
```