Editing 1691 - Arbore 1

= Cerința =
Se dă un arbore (graf conex aciclic) cu <code>N</code> noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

= Date de intrare =
Fișierul de intrare <code>arbore1IN.txt</code> conține pe prima linie numărul natural <code>N</code>, reprezentând numărul de noduri ale arborelui. Pe următoarele <code>N-1</code> linii se vor afla câte două numere <code>X</code> și <code>Y</code>, cu semnificația că există o muchie între nodurile <code>X</code> și <code>Y</code>.

= Date de ieșire =
Fișierul de ieșire <code>arbore1OUT.txt</code> va conține pe prima linie două numere naturale reprezentând numărul maxim de componente conexe pe care îl putem obține, respectiv numărul de moduri în care putem obține acest număr de componente conexe modulo <code>10^9+7</code> (adică restul împărțirii acestui număr la <code>1000000007</code>).În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* Se acordă 40% din punctajul unui test dacă numărul maxim de componente conexe este corect.
* Se acordă 60% din punctajul unui test dacă numărul de moduri este corect.
* Pentru 20% din teste <code>N ≤ 20</code>
* Pentru alte 30% din teste <code>N ≤ 1000</code>

= Exemplul 1: =
<code>arbore1IN.txt</code>
 6
 1 2
 1 3
 1 4
 4 5
 4 6
<code>arbore1OUT.txt</code>
 4 1

=== Explicație ===
Se șterg nodurile <code>1</code> și <code>4</code>. Nicio altă submulțime de noduri șterse nu produce <code>4</code> sau mai multe componente conexe.

== Exemplul 2 ==
<code>arbore1IN.txt</code>
 100001
 1 2
 1 3
 1 4
 4 5
 4 6
<code>arbore1OUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict

N = 100100
mod = 1000000007

v = defaultdict(list)
D = [[0] * N for _ in range(3)]
W = [[1] * N for _ in range(3)]

def check_constraints(n):
    if not (1 <= n <= 100000):
        with open("arbore1OUT.txt", "w") as output_file:
            output_file.write("Datele nu corespund restrictiilor impuse")
        exit()

def dfs(x, p):
    D[1][x] = 1
    D[0][x] = 0
    D[2][x] = 1
    W[1][x] = 1
    W[0][x] = 1
    W[2][x] = 1
    
    for it in v[x]:
        if it != p:
            dfs(it, x)
    
    # Cazul 1. Stergem nodul
    for it in v[x]:
        if it != p:
            D[0][x] += D[2][it]
            W[0][x] *= W[2][it]
            W[0][x] %= mod
    
    # Cazul 2. Nu stergem nodul
    for it in v[x]:
        if it != p:
            if D[0][it] + 1 == D[1][it]:
                W[1][x] *= (W[0][it] + W[1][it]) % mod
                W[1][x] %= mod
                D[1][x] += D[0][it]
            elif D[0][it] + 1 < D[1][it]:
                W[1][x] *= W[1][it]
                W[1][x] %= mod
                D[1][x] += D[1][it] - 1
            else:
                W[1][x] *= W[0][it]
                W[1][x] %= mod
                D[1][x] += D[0][it]
    
    # Calculam solutia pentru acest subarbore stiind cele 2 cazuri
    D[2][x] = max(D[1][x], D[0][x])
    if D[1][x] == D[0][x]:
        W[2][x] = (W[1][x] + W[0][x]) % mod
    elif D[1][x] > D[0][x]:
        W[2][x] = W[1][x]
    else:
        W[2][x] = W[0][x]

def main():
    with open("arbore1IN.txt", "r") as input_file:
        n = int(input_file.readline().strip())
        check_constraints(n)
        
        for _ in range(n-1):
            x, y = map(int, input_file.readline().strip().split())
            v[x].append(y)
            v[y].append(x)

    dfs(1, 0)

    with open("arbore1OUT.txt", "w") as output_file:
        output_file.write(f"{D[2][1]} {W[2][1]}")

if __name__ == "__main__":
    main()

</syntaxhighlight>