Kungarikesuppdelning

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.

Tyvärr har den gamla kungen dött, utan att utse en efterträdare. Detta ledde till ett inbördeskrig mellan rikets $P$ grevar (numrerade från $0$ till $P - 1$) som alla ville ha kontroll över riket.

Efter ett långt och hemskt krig insåg grevarna att ingen ensam greve kunde vinna kriget. De gick med på ett fredsavtal, där riket delas upp i $P$ delar, en per greve. Delarna måste vara så att om två städer $a$ och $b$ tillhör samma greve, så måste alla städer på den unika vägen mellan $a$ och $b$ också tillhöra greven. Eftersom ingen greve vill lämnas maktlös måste varje greve få minst en stad.

Ingen greve vill heller få mindre än någon annan, så det totala värdet av alla städer måste vara detsamma för varje greve. Det totala värdet är summan av varje stads värde.

Exempel

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

Figure 1: Illustration av exemplet

Varje stad har ett värde, givet inom parenteser efter stadens nummer.

Vi vill dela in riket i $P = 3$ delar. En möjlig indelning är $(0, 2)$, $(3)$, $(1, 4)$. Varje dels värde blir då $-4 + 3 = -1$, $-1$, och $3 - 4 = -1$, så alla delar i denna uppdelning har samma värde.

Notera att $(0, 1)$ $(3)$, $(2, 4)$ inte är en giltig uppdelning trots att varje del har samma värde. Detta är för att vägen mellan städerna $0$ och $1$ består av $1, 4, 2, 0$, men städerna $4$ och $2$ tillhör en annan greve.

Uppgift

Uppgiften är att beräkna en uppdelning av kungariket som beskriven. Du ska implementera funktionen division(N, P, C, F, T).

• division(N, P, C, F, T) - denna funktion kommer anropas exakt en gång av domaren.

  • N: antalet städer i kungariket.

  • P: antalet delar vi vill dela in kungariket i.

  • C: en array med $N$ element. C[i] ($0 \le i < N$) innehåller den $i$:te stadens värde.

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

  • T: en array med $N - 1$ element. T[i] ($0 \le i < N - 1$) innehåller den andra staden som den $i$:te vägen går mellan.

  • Det är alltid möjligt att resa mellan varje par av städer med någon sekvens av vägar.

  • $|C[i]| < 10^9$

  • Funktionen ska returnera 1 om det existerar en sådan indelning, och 0 om det är omöjligt.

Dessutom ska du göra exakt ett anrop till parts(S) för att konstruera din indelning.

• parts(S) - denna funktion ska anropas exakt en gång.

  • S: en array med $N$ element. $S[i]$ $(0 \le i < N)$ ska innehålla numret på den greve som får den $i$:te staden.

  • Denna funktion har inget returvärde.

Ett kodskelett som innehåller funktionen du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/kingdom.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.

Om din uppdelning är felaktig, men du avgör korrekt om en uppdelning existerar, får din lösning $50\% $ av poängen för en grupp.

Indataformat

Exempeldomaren läser indata i följande format:

• line $1$: N P

• line $2$: C[0] C[1] .. C[N - 1]

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

• line $4$: T[0] T[1] .. T[N - 2]

Utdataformat

Exempeldomaren skriver först ut en rad med värdet som returnerades av division(N, P, C, F, T). Nästa rad innehåller de $N$ heltalen som gavs i anropet till parts(R).

5 3
-4 3 3 -1 -4
0 1 2 3
2 4 4 4

1
0 1 0 2 1