1200 – Spiriduși

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 spiridusi.in 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 spiridusi.out 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:

spiridusi.in

6 8
2 4 6 2 4 1 
3 10 11 -2 4 5
1 2
2 3
2 4
4 5
4 6

spiridusi.out

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.

Rezolvare

<syntaxhighlight lang="python3"> import sys

nmax = 10**5 logmax = 17

dx = [[] for _ in range(nmax+5)] up = [[0] * (logmax+5) for _ in range(nmax+5)] sum_val = [[0] * (logmax+5) for _ in range(nmax+5)] Psum = [[0] * (logmax+5) for _ in range(nmax+5)]

def build(node, father):

   for i in range(1, logmax+1):
       up[node][i] = up[up[node][i-1]][i-1]
       sum_val[node][i] = sum_val[node][i-1] + sum_val[up[node][i-1]][i-1]
       Psum[node][i] = Psum[node][i-1] + Psum[up[node][i-1]][i-1]
   for next_node in dx[node]:
       if next_node != father:
           up[next_node][0] = node
           sum_val[next_node][0] = s[node]
           Psum[next_node][0] = p[node]
           build(next_node, node)

def dfs(node, father):

   for next_node in dx[node]:
       if next_node != father:
           if s[next_node] > c:
               dfs(next_node, node)
           else:
               next_S = s[next_node]
               next_P = p[next_node]
               next_A = next_node
               for i in range(logmax, -1, -1):
                   if up[next_A][i] and next_S + sum_val[next_A][i] <= c:
                       next_S += sum_val[next_A][i]
                       next_P += Psum[next_A][i]
                       next_A = up[next_A][i]
               dp[next_node] = max(next_P, p[next_node])
               dfs(next_node, node)

if __name__ == "__main__":

   sys.stdin = open("spiridusi.in", "r")
   sys.stdout = open("spiridusi.out", "w")

   n, c = map(int, input().split())
   s = [0] * (nmax+5)
   p = [0] * (nmax+5)
   dp = [0] * (nmax+5)
   ans = 0

   s_input = input().split()
   p_input = input().split()

   for i in range(1, n+1):
       s[i] = int(s_input[i-1])
   for i in range(1, n+1):
       p[i] = int(p_input[i-1])
   for i in range(1, n):
       x, y = map(int, input().split())
       dx[x].append(y)
       dx[y].append(x)
   build(1, 0)
   if s[1] <= c:
       dp[1] = p[1]
   dfs(1, 0)
   for i in range(1, n+1):
       ans = max(ans, dp[i])
   print(ans)

</syntaxhighlight>