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}](/problems/cities/file/statement/sv/img-0001.png)
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 |
