Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile `p` din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în `p` este maximă. = Date de intrare = Fișierul de intrare `sumsubmaxIN.txt` conține pe prima linie numărul de noduri `n`. Pe a doua linie se află vec...

2024-01-02T21:12:38Z

Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă. = Date de intrare = Fișierul de intrare <code>sumsubmaxIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe a doua linie se află vec...

New page

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă.

= Date de intrare =
Fișierul de intrare <code>sumsubmaxIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe a doua linie se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe linia a treia se află, în ordine, valorile asociate nodurilor din arbore, separate și ele prin spații.

= Date de ieșire =
Fișierul de ieșire <code>sumsubmaxOUT.txt</code> va conține, în ordine crescătoare, nodurile <code>p</code> din arbore pentru care suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>p</code> este maximă, separate printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* valorile asociate nodurilor din arbore sunt numere întregi din intervalul <code>[-1000,1000]</code>

== Exemplul 1 ==
sumsubmaxIN.txt:

8

4 3 0 3 2 1 2 1

-3 2 -7 4 0 3 3 1

sumsubmaxOUT.txt:

2 4

Explicație:

În subarborii cu rădăcina în <code>2</code> și <code>4</code> suma valorilor asociate nodurilor este <code>5</code> și este maximă.

== Exemplul 2 ==
sumsubmaxIN.txt:

101

4 3 0 3 2 1 2 1

-3 2 -7 4 0 3 3 1

Output:

Invalid input. Please check the constraints.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_input(n, t, val):
if not (1 <= n <= 100):
return False

if len(t) != n + 1 or len(val) != n + 1:
return False

for i in range(1, n + 1):
if not (-1000 <= val[i] <= 1000):
return False

return True

def dfs(k):
v[k] = 1
for i in range(1, n + 1):
if i < len(t) and t[i] == k and not v[i]:
dfs(i)

# Read input from file
with open("sumsubmaxIN.txt", "r") as fin:
n = int(fin.readline().strip())
t = [0] + list(map(int, fin.readline().split())) # Adjust for 1-based indexing
val = [0] + list(map(int, fin.readline().split())) # Adjust for 1-based indexing

# Check input constraints
if not is_valid_input(n, t, val):
print("Invalid input. Please check the constraints.")
exit()

smax = [0] * (n + 1)

# Perform DFS and calculate sum of values for each subtree
for i in range(1, n + 1):
v = [0] * (n + 1)
dfs(i)
for j in range(1, n + 1):
if j < len(v) and v[j] == 1:
smax[i] += val[j]

# Find the maximum sum
ma = max(smax)

# Write output to file
with open("sumsubmaxOUT.txt", "w") as fout:
for i in range(1, n + 1):
if smax[i] == ma:
fout.write(f"{i} ")

</syntaxhighlight>

0651 – Sum Sub Max - Revision history