Brianna Waltner: Pagină nouă: == Cerinţa == Țăranul Ion are în livada sa '''N''' pomi, fiecare cu '''v[i]''' mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi. Ion pornește din pomul lui...

2024-01-03T18:19:11Z

Pagină nouă: == Cerinţa == Țăranul Ion are în livada sa '''N''' pomi, fiecare cu '''v[i]''' mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi. Ion pornește din pomul lui...

New page

== Cerinţa ==
Țăranul Ion are în livada sa '''N''' pomi, fiecare cu '''v[i]''' mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi.

Ion pornește din pomul lui preferat, pomul '''1''', și se deplasează spre unul din vecinii lui. Pentru că nu este foarte inteligent, atunci când Ion se află la un pom, el se va deplasa către pomul vecin care are cele mai multe mere, fără să ia în calcul ceilalți meri din livadă. Dacă doi pomi au același număr de mere, atunci Ion se va deplasa spre pomul cu numărul de ordine mai mic.

Ajutați-l pe Ion să afle câte mere va aduna folosind metoda sa!
== Date de intrare ==
Pe prima linie a fișierului de intrare '''merein.txt''' se află un număr natural '''N''', reprezentând numărul de pomi din livadă; pe linia a doua se află '''N''' valori '''v[i]''', reprezentând numărul de mere din pomul '''i'''. Pe următoarele '''N-1''' linii se află câte o pereche de numere '''x y''', cu semnificația că există o cărare de la pomul '''x''' la pomul '''y'''.
== Date de ieșire ==
Fișierul de ieșire '''mereout.txt''' va conține pe prima linie numărul '''S''', reprezentând numărul total de mere culese.
== Restricţii şi precizări ==
* '''1 &les; n &les; 1000'''
* '''1 &les; v[i] &les; 10000'''
== Exemplul 1 ==
;'''merein.txt'''
6
3 1 2 3 2 1
1 2
1 3
2 4
2 5
2 6
;'''mereout.txt'''
Datele de intrare corespund restrictiilor impuse
5
== Exemplul 2 ==
;'''merein.txt'''
65000
3 1 2 3 2 1
1 2
1 3
2 4
2 5
2 6
;'''mereout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def dfs(node, parent):
global ans, maxv, idx, visit, g, apple
visit[node] = True
for neighbour in g[node]:
if neighbour != parent and not visit[neighbour]:
dfs(neighbour, node)
if apple[neighbour] > maxv[node]:
maxv[node] = apple[neighbour]
idx[node] = neighbour

def solve():
global ans, maxv, idx, visit, g, apple
dfs(1, 0)
node = 1
while node:
ans += apple[node]
node = idx[node]

if __name__ == "__main__":
g = defaultdict(list)
ans = 0

with open('merein.txt', 'r') as fin:
N = int(fin.readline().strip())
if N < 1 or N > 1000:
with open('mereout.txt', 'w') as fout:
fout.write("Datele de intrare nu corespund restrictiilor impuse")
exit(0)
apple = [0] + list(map(int, fin.readline().split()))
maxv = [0]*(N+1)
idx = [0]*(N+1)
visit = [False]*(N+1)

for _ in range(N-1):
u, v = map(int, fin.readline().split())
g[u].append(v)
g[v].append(u)

solve()

with open('mereout.txt', 'w') as fout:
fout.write(str(ans) if ans else "Datele de intrare corespund restrictiilor impuse")
</syntaxhighlight>

== Explicatie ==
Ion va culege merele din pomii '''1 3''', obținând '''3+2=5''' mere.

0550 - Mere - Revision history