Problem R
Städer

I ett fjärran kungarike finns $N$ städer numrerade från $0$ till $N-1$. Städerna är anslutna till varandra med $N-1$ gator som går att använda i båda riktningarna. Alla gator är lika långa och ansluter exakt två städer på ett sådant sätt att det finns en unik väg mellan alla par av städer.

För två städer $A$ och $B$, låt $L(A,B)$ vara antalet gator på den unika vägen mellan städerna $A$ och $B$. Givet ett heltal $K$, hur många par av städer $A,B$ finns det så att $L(A,B)=K$?

Exempel

Låt kungariket ha $N=5$ städer, anslutna av gator som i figuren:

Figure 1: Illustration av exemplet

Följande 4 par har en enda gata mellan sig: $(0,1),(0,2),(0,4),(3,4)$.

Följande 4 par har två gator mellan sig: $(0,3),(1,2),(1,4),(2,4)$.

Följande 2 par har tre gator mellan sig: $(1,3),(2,3)$.

Det innebär att för $K=1,2,3$ skulle svaren vara $4,4,2$ respektive.

Uppgift

Uppgiften är att beräkna hur många par av städer som har precis $K$ gator mellan sig. Du ska implementera funktionen paths(N, K, F, T).

• paths(N, K, F, T) - den här funktionen kommer att anropas precis en gång av domaren.

  • N: antalet städer i kungariket.

  • K: antalet vägar mellan par av städer som vi är intresserade av.

  • F: en array med $N-1$ element F[i] ($0\le i<N$) innehåller den ena staden som den $i$:te gatan är ansluten till.

  • F: en array med $N-1$ element F[i] ($0\le i<N$) innehåller den andra staden som den $i$:te gatan är ansluten till.

  • Det är alltid möjligt att färdas mellan varje par av städer med hjälp av gatorna.

  • Funktion ska returnera antalet par av städer med precis $K$ gator mellan sig.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/cities.zip.

Delpoäng

Problemet består av flera grupper av testfall. Varje grupp ger ett visst antal poäng och för att klara det måste du klara alla testfall i gruppen.

Input format

Exempeldomaren läser indata i följande format:

• rad $1$: N K

• rad $2$: F[0] F[1] .. F[N - 2]

• rad $3$: T[0] T[1] .. T[N - 2]

Output format

Exempeldomaren skriver ut en rad med värdet som returnerades av paths(N, K, F, T).

5 2
0 0 0 3
1 2 4 4

4