Editing 0649 – Subarbori

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați câte perechi de noduri neterminale distincte <code>p q</code> din arbore au proprietatea că subarborele cu rădăcina în <code>p</code> și cel cu rădăcina în <code>q</code> au același număr de noduri.

= Date de intrare =
Fișierul de intrare <code>subarboriIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>subarboriOUT.txt</code> va conține pe prima linie valoarea cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

= Exemplul 1: =
<code>subarboriIN.txt</code>
 8
 4 3 0 3 2 1 2 1
<code>subarboriOUT.txt</code>
 1

= Explicație =
Singura pereche de noduri neterminale pentru care subarborii au același număr de noduri este <code>2 1</code>. Subarborii cu rădăcina în <code>2</code> și <code>1</code> au câte <code>3</code> noduri fiecare.

== Exemplul 2: ==
<code>subarboriIN.txt</code>
 101
 4 3 0 3 2 1 2 1
<code>subarboriOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
class NodArbore:
    def __init__(self, valoare):
        self.valoare = valoare
        self.copii = []

def construieste_arbore(tati):
    noduri = [NodArbore(i) for i in range(len(tati))]
    
    for i, tata in enumerate(tati):
        if tata != 0:
            noduri[tata - 1].copii.append(noduri[i])
    
    return noduri[0]  # returnează rădăcina arborelui

def numara_subarbori_cu_acelasi_numar_de_noduri(nod):
    if not nod.copii:
        return 1, {1: 1}  # tuplu: (număr de noduri, dicționar cu numărul de subarbori de acea dimensiune)
    
    total_noduri = 1
    dimensiuni_subarbori = {}
    
    for copil in nod.copii:
        dimensiune_copil, dimensiuni_subarbori_copil = numara_subarbori_cu_acelasi_numar_de_noduri(copil)
        total_noduri += dimensiune_copil
        
        for dimensiune, numar in dimensiuni_subarbori_copil.items():
            dimensiuni_subarbori[dimensiune] = dimensiuni_subarbori.get(dimensiune, 0) + numar
        
    dimensiuni_subarbori[total_noduri] = dimensiuni_subarbori.get(total_noduri, 0) + 1
    
    return total_noduri, dimensiuni_subarbori

def verificare_restricții(n):
    if not (1 <= n <= 100):
        with open("subarboriOUT.txt", "w") as fisier_iesire:
            fisier_iesire.write("Datele nu corespund restrictiilor impuse")
        exit()

def main():
    with open("subarboriIN.txt", "r") as fisier_intrare:
        n = int(fisier_intrare.readline().strip())
        verificare_restricții(n)
        tati = list(map(int, fisier_intrare.readline().strip().split()))

    radacina = construieste_arbore(tati)
    _, dimensiuni_subarbori = numara_subarbori_cu_acelasi_numar_de_noduri(radacina)
    
    rezultat = sum(numar * (numar - 1) // 2 for numar in dimensiuni_subarbori.values())
    
    with open("subarboriOUT.txt", "w") as fisier_iesire:
        fisier_iesire.write(str(rezultat))

if __name__ == "__main__":
    main()

</syntaxhighlight>