Hide

Problem R
Städer

Languages en sv

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:

\includegraphics[width=0.3\textwidth ]{sample.png}
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.

Grupp

Poäng

Gränser

1

9

$1 \le K \le N \le 100$

2

19

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

3

34

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

4

38

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

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).

Sample Input 1 Sample Output 1
5 2
0 0 0 3
1 2 4 4
4