1200 - Spiriduși

Enunt

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din N camere, unite între ele prin N-1 culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera 1. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră i s-au stabilit s[i] spiriduși de praf.

Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere a și b (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera b trece prin camera a. Fetele vor merge apoi din camera a în camera b pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele a și b. După ce fetele ajung în camera b, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

Fetele au stabilit pentru fiecare cameră i un coeficient p[i] care reprezintă cât de plăcută ar fi camera i pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de C spiriduși ai prafului din camerele prin care trec.

Cerința

Cunoscând valorile lui N și C, numărul de spiriduși ai prafului s[i], coeficienții p[i] pentru fiecare cameră i, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

Date de intrare

Pe prima linie a fișierului de intrare spiridusiin.txt se vor afla două numere naturale N și C cu semnificația din enunț. Pe a doua linie se vor afla N numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând numărul de spiriduși s[i] aflați în camera i. Pe a treia linie se vor afla N numere întregi separate prin câte un spațiu, al i-lea dintre acestea reprezentând coeficientul p[i] al camerei i. Pe următoarele N-1 linii se vor afla câte două numere întregi x și y separate printr-un spațiu, semnificând existența unui culoar ce unește camerele x și y.

Date de ieșire

În fișierul de ieșire spiridusiout.txt se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților p ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

Restricții și precizări

• 1 ⩽ N ⩽ 100 000
• 1 ⩽ C ⩽ 20 000 000
• 1 ⩽ s[i] ⩽ 20 000 000, pentru orice i, 1 ⩽ i ⩽ N.
• -10 000 ⩽ p[i] ⩽ 10 000, pentru orice i, 1 ⩽ i ⩽ N.
• 1 ⩽ x, y ⩽ N
• Pentru 20% din teste, fiecare cameră are maximum 2 vecini.
• Pentru 30% din teste, N ≤ 1 000.
• Se garantează că pentru orice cameră x, numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera 1 la camera x nu depășește 1 000 000 000.

Exemplu 1

spiridusiin.txt

6 8

2 4 6 2 4 1

3 10 11 -2 4 5

1 2

2 3

2 4

4 5

4 6

spriridusiout.txt

13

Explicație

"Dacă alegem camerele a = 2 și b = 6, obținem un spațiu de joacă format din camerele 2, 4 și 6. "Numărul total de spiriduși goniți din aceste camere este 4 + 2 + 1 = 7, care este mai mic sau egal decât C = 8. "Suma coeficienților p ai acestor camere este 10 + (-2) + 5 = 13, maximul posibil ce se poate obține.

Exemplu 2

spiridusiin.txt

0 0

spriridusiout.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 1200 - Spiridusi

def read_input(file_name):

   try:
       with open(file_name, 'r') as file:
           N, C = map(int, file.readline().split())
           s = list(map(int, file.readline().split()))
           p = list(map(int, file.readline().split()))
           connections = [tuple(map(int, file.readline().split())) for _ in range(N - 1)]

           if not (1 <= N <= 100000 and 1 <= C <= 20000000 and all(1 <= elem <= 20000000 for elem in s) and
                   all(-10000 <= elem <= 10000 for elem in p) and all(
                       1 <= elem <= N for pair in connections for elem in pair)):
               raise ValueError("Numerele nu respectă restricțiile.")

           return N, C, s, p, connections
   except Exception as e:
       print(f"Nu au fost respectate cerințele impuse: {str(e)}")
       return None

def solve(N, C, s, p, connections):

   # Construim graful
   graph = {}
   for x, y in connections:
       if x not in graph:
           graph[x] = []
       if y not in graph:
           graph[y] = []
       graph[x].append(y)
       graph[y].append(x)

   # Funcție pentru calculul sumei maxime a coeficienților
   def dfs(node, parent, current_path, current_dust):
       nonlocal max_sum
       current_path.append(node)

       # Calculăm suma pentru nodul curent
       current_sum = sum(p[i - 1] for i in current_path)
       max_sum = max(max_sum, current_sum)

       # Parcurgem vecinii nodului curent
       for neighbor in graph[node]:
           if neighbor != parent:
               # Calculăm numărul total de spiriduși de praf pe drumul curent
               total_dust = current_dust + s[neighbor - 1]
               # Verificăm dacă numărul de spiriduși nu depășește C
               if total_dust <= C:
                   dfs(neighbor, node, current_path[:], total_dust)

   max_sum = 0
   dfs(1, 0, [], s[0])

   return max_sum

1. Citim datele de intrare

input_data = read_input("spiridusiin.txt") if input_data is not None:

   N, C, s, p, connections = input_data

   # Calculăm rezultatul
   result = solve(N, C, s, p, connections)

   # Scriem rezultatul în fișierul de ieșire
   with open("spiridusiout.txt", "w") as file:
       file.write(str(result))

</syntaxhighlight>