Editing 1200 – Spiriduși

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din <code>N</code> camere, unite între ele prin <code>N-1</code> culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera <code>1</code>. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră <code>i</code> s-au stabilit <code>s[i]</code> 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 <code>a</code> și <code>b</code> (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera <code>b</code> trece prin camera <code>a</code>. Fetele vor merge apoi din camera <code>a</code> în camera <code>b</code> 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 <code>a</code> și <code>b</code>. După ce fetele ajung în camera <code>b</code>, 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ă <code>i</code> un coeficient <code>p[i]</code> care reprezintă cât de plăcută ar fi camera <code>i</code> pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de <code>C</code> spiriduși ai prafului din camerele prin care trec.

= Cerința =
Cunoscând valorile lui <code>N</code> și <code>C</code>, numărul de spiriduși ai prafului <code>s[i]</code>, coeficienții <code>p[i]</code> pentru fiecare cameră <code>i</code>, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților <code>p</code> 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 <code>spiridusi.in</code> se vor afla două numere naturale <code>N</code> și <code>C</code> cu semnificația din enunț. Pe a doua linie se vor afla <code>N</code> numere naturale separate prin câte un spațiu, al <code>i</code>-lea dintre acestea reprezentând numărul de spiriduși <code>s[i]</code> aflați în camera <code>i</code>. Pe a treia linie se vor afla <code>N</code> numere întregi separate prin câte un spațiu, al <code>i</code>-lea dintre acestea reprezentând coeficientul <code>p[i]</code> al camerei <code>i</code>. Pe următoarele <code>N-1</code> linii se vor afla câte două numere întregi <code>x</code> și <code>y</code> separate printr-un spațiu, semnificând existența unui culoar ce unește camerele <code>x</code> și <code>y</code>.

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

= Restricții și precizări =

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

= Exemplu: =
<code>spiridusi.in</code>
 6 8
 2 4 6 2 4 1 
 3 10 11 -2 4 5
 1 2
 2 3
 2 4
 4 5
 4 6
<code>spiridusi.out</code>
 13

= Explicație =
Dacă alegem camerele <code>a = 2</code> și <code>b = 6</code>, obținem un spațiu de joacă format din camerele <code>2</code>, <code>4</code> și <code>6</code>.

Numărul total de spiriduși goniți din aceste camere este <code>4 + 2 + 1 = 7</code>, care este mai mic sau egal decât <code>C = 8</code>.

Suma coeficienților <code>p</code> ai acestor camere este <code>10 + (-2) + 5 = 13</code>, 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>