def collect_coins_brute_force(edges, coins_on_nodes):
    number_of_nodes = len(coins_on_nodes)
    maximum_coins_collected = 0

    # Iterate through all possible starting nodes
    for start_node in range(number_of_nodes):
        # Explore paths starting from the current node
        current_maximum = explore_all_paths(start_node, edges, coins_on_nodes)
        maximum_coins_collected = max(maximum_coins_collected, current_maximum)

    return maximum_coins_collected

def explore_all_paths(current_node, edges, coins_on_nodes):
    maximum_coins = 0

    def depth_first_search(node, visited_nodes, current_coins):
        nonlocal maximum_coins
        visited_nodes.add(node)
        current_coins += coins_on_nodes[node]

        maximum_coins = max(maximum_coins, current_coins)

        # Explore all neighbors of the current node
        neighbors = get_neighbors(node, edges)

        # DFS for each unvisited neighbor
        for neighbor in neighbors:
            if neighbor not in visited_nodes:
                depth_first_search(neighbor, visited_nodes.copy(), current_coins)

    # Start the depth-first search
    depth_first_search(current_node, set(), 0)
    
    return maximum_coins

def get_neighbors(node, edges):
    neighboring_nodes = []
    for edge_start, edge_end in edges:
        if edge_start == node:
            neighboring_nodes.append(edge_end)
        elif edge_end == node:
            neighboring_nodes.append(edge_start)
    return neighboring_nodes

# This represents an example usage of the above code.
def example_usage():
    edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]]
    coins_on_nodes = [0, 1, 0, 0, 0, 1, 0]
    result = collect_coins_brute_force(edges, coins_on_nodes)
    print(f"Maximum coins collected: {result}")

if __name__ == "__main__":
    example_usage()

def collect_coins_in_a_tree(number_of_nodes, edges, has_coin):
    adjacency_list = [[] for _ in range(number_of_nodes)]
    for node1, node2 in edges:
        adjacency_list[node1].append(node2)
        adjacency_list[node2].append(node1)

    nodes_to_keep = [True] * number_of_nodes

    while True:
        nodes_to_remove = []

        # Identify useless leaves
        for node_index in range(number_of_nodes):
            if nodes_to_keep[node_index] and len(adjacency_list[node_index]) == 1 and not has_coin[node_index]:
                nodes_to_remove.append(node_index)

        # Identify useless single-connection nodes
        for node_index in range(number_of_nodes):
            if nodes_to_keep[node_index] and len(adjacency_list[node_index]) <= 1 and not has_coin[node_index]:
                nodes_to_remove.append(node_index)

        if not nodes_to_remove:
            break

        for node_to_remove in nodes_to_remove:
            if nodes_to_keep[node_to_remove]:
                nodes_to_keep[node_to_remove] = False

                # This section updates the adjacency list
                # after removing a node.
                for neighbor_node in adjacency_list[node_to_remove]:
                    adjacency_list[neighbor_node].remove(node_to_remove)

                adjacency_list[node_to_remove] = []

    # Count remaining edges
    edge_count = 0
    for node_index in range(number_of_nodes):
        if nodes_to_keep[node_index]:
            edge_count += len(adjacency_list[node_index])

    # Each edge is counted twice, so divide by 2.
    return edge_count // 2