teamcoding
Day1 Tasks

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

Italian (ITA)

C. Team Coding
Nome problema

Team Coding

Limite di tempo

4 secondi

Limite di memoria

1 gigaottetto

L'azienda Eindhoven Gigantic Open-Source Institute (EGOI) è strutturata in modo molto gerarchico.
A parte l'amministratore delegato Anneke, ciascuno degli altri N − 1 dipendenti dell'azienda ha uncapo unico e non ci sono strutture cicliche nella gerarchia. Puoi rappresentare la gerarchiaaziendale con un albero radicato nel vertice corrispondente ad Anneke. Poiché si tratta diun'azienda diversiﬁcata, i dipendenti scrivono codice in K linguaggi di programmazione diversi,
ma ogni dipendente ha esattamente un linguaggio di programmazione preferito.
Anneke ha un nuovo progetto molto importante su cui far lavorare un team della sua azienda.
Vuole investire quante più risorse possibili in questo progetto. Per decidere il team che ci lavorerà,
procede come segue:
1. Sceglie una persona che guidi il team. Questo deﬁnirà anche il linguaggio diprogrammazione in cui è scritto il progetto. Ogni dipendente che si trova nel sottoalbero
sotto il team leader e preferisce il suo stesso linguaggio di programmazione lavorerà sul
problema.
2. Aumenta il numero di dipendenti che lavorano al progetto, spostando i dipendenti che
preferiscono lo stesso linguaggio di programmazione del team leader nel suo team.
Per massimizzare il numero di dipendenti che lavorano al progetto, può eseguire i seguenti scambi
un numero qualsiasi di volte:
1. Sceglie due dipendenti:
Un dipendente che si trova attualmente nel sottoalbero del team leader e non
preferisce lo stesso linguaggio di programmazione del team leader.
Un dipendente che non si trova in questo sottoalbero al momento e preferisce il suo
stesso linguaggio di programmazione. Inoltre, questo dipendente deve essere allo
stesso livello dell'altro dipendente scelto; ovvero, deve avere lo stesso numero disuperiori nella catena di comando ﬁno ad Anneke. Se rappresenti la gerarchiaaziendale come un albero, allora i due dipendenti sono allo stesso livello dell'albero.

teamcoding (1 of 5)

2. Quei due dipendenti (e solo loro – nessun altro dipendente) cambiano posizione nella
gerarchia aziendale. Nota che i dipendenti sottoposti ai due dipendenti interessati
rimangono al loro posto e cambiano solo il loro capo. Nell'esempio seguente, con ildipendente 4 scelto come capogruppo, possiamo scambiare i dipendenti 3 e 2 ma non i
dipendenti 1 e 8.

Trova il numero massimo di dipendenti che possono lavorare al nuovo progetto e il numero
minimo di operazioni di cambio necessarie per raggiungere questo numero.

Input
La prima riga dell'input contiene due numeri interi, N e K , il numero di dipendenti di EGOI e ilnumero di linguaggi di programmazione che i dipendenti potrebbero utilizzare.
I dipendenti di EGOI sono numerati da 0 a N − 1 e Anneke, l'amministratore delegato, ha il
numero 0. La riga successiva contiene N numeri interi ℓi con 0 ≤ ℓi < K , i linguaggi diprogrammazione preferiti dai dipendenti.
Le successive N − 1 righe contengono la struttura aziendale. La i -esima riga contiene un numero
intero bi con 0 ≤ bi < N , il capo diretto del i -esimo dipendente. Nota che i va da 1 a N − 1(inclusi), poiché Anneke, l'amministratore delegato, non ha un capo.

OutputStampa una singola riga con due numeri interi, P e S , il numero massimo di dipendenti (incluso ilteam leader) che lavorano al nuovo progetto che puoi ottenere con un numero qualsiasi di scambi
e il numero minimo di scambi necessari per ottenerlo.

Limiti e punteggio
1 ≤ N ≤ 105 .
1 ≤ K ≤ N.
teamcoding (2 of 5)

La tua soluzione verrà testata su un set di subtask, ognuno dei quali vale un certo numero di punti.
Ogni subtask contiene un set di testcase. Per ottenere i punti per un subtask, devi risolvere tutti itestcase nel subtask.
GruppoPunteggio

Limiti

112Il capo diretto del dipendente i è i − 1 per tutti gli 1 ≤ i < N .

219K ≤2327423N ≤ 2 000

519

Nessun limite aggiuntivo

Per ogni linguaggio di programmazione, ci sono al massimo 10dipendenti che lo preferiscono

EsempiNei primi due esempi, la struttura aziendale appare come segue, dove il pattern codiﬁca illinguaggio di programmazione (0 = "tratteggiato", 1 = "puntini", 2 = "bianco"):Nel primo esempio, possiamo scegliere il dipendente 1 come team leader con il dipendente 4 che
preferisce lo stesso linguaggio di programmazione; non ci sono possibili scambi per migliorare lasituazione.
Nel secondo esempio, l'intera azienda ha 3 dipendenti che preferiscono il linguaggio 0 che è anche
il linguaggio preferito di Anneke, quindi scegliendo Anneke come team leader si ottiene un teamdi dimensioni 3 senza bisogno di scambi.

teamcoding (3 of 5)

Nel terzo esempio, scegliamo il dipendente 4 come team leader e poi possiamo far cambiare teamai dipendenti 1 e 8 e 2 e 3 per ottenere un totale di 4 dipendenti che preferiscono lo stesso
linguaggio di 4, ovvero il linguaggio 2 (plain). Nell'esempio 4, il punteggio massimo può essereottenuto scegliendo il dipendente 6 come team leader e cambiando i dipendenti 4 e 7 e 1 e 5. Notache non possiamo cambiare i dipendenti 6 e 3 prima di scegliere il team leader per ottenere unpunteggio di 4 perché dobbiamo prima ﬁssare il team leader.

teamcoding (4 of 5)

Input5 30 1 2 2 1Output

2 00123

4 23 00 1 0 00019 34 20 0 2 1 2 0 2 1 2481041078 3

3 20 2 1 2 2 1 1 16306303teamcoding (5 of 5)