Editing 1200 - Spiriduși (section)

== Rezolvare ==
<syntaxhighlight lang="python" line>
#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

# 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>