BIG = 1e18


class BidirectedGraph:

    def __init__(self, values):
        self.n = len(values)
        self.values = values # В инит передаем массив значений вершин
        self.edges = [[] for i in range(self.n)]

    def add_edge(self, u, v): # Когда добавляется ребро, создаем ребро из u IN v, v IN u
        # тк это двунаправленный граф
        u -= 1
        v -= 1
        self.edges[u].append(v)
        self.edges[v].append(u)

    def find_max_path_dfs(self, v, parent):
        # Рекурсия будет считать ответ для поддерева вершины v
        # И этот ответ это будет максимум из ответа всех поддеревьев
        # И какого-то пути из одного поддерева через нашу вершину в другой
        # Будем использовать вспомогательный массив dp
        # В котором будет хранится наилучший путь, если будем идти от этой вершины
        # Как-нибудь вниз
        mx1, mx2, ans = -BIG, -BIG, -BIG
        self.dp[v] = self.values[v]  # Изначально это вершина графа
        for child in self.edges[v]:  # Итерируемся по детям
            if child == parent:  # Смотри, чтоб наш ребенок не был предком, чтоб не зациклиться
                continue
            child_ans = self.find_max_path_dfs(child, v)  # Вызываем рекурсию,
            # И находим ответ поддерева чайлда
            # Смотрим, что является максимальным из нашего
            ans = max(ans, child_ans)
            # Пытаемся улучшить ответ для нашего поддерева
            self.dp[v] = max(
                self.dp[v],
                max(0, self.dp[child]) + self.values[v]
            )
            if mx1 <= self.dp[child]: # Находим два самых максимальных dp[child]
                mx2 = mx1
                mx1 = self.dp[child]
            elif mx2 < self.dp[child]:
                mx2 = self.dp[child]

        ans = max(ans, max(0, mx1) + max(0, mx2) + self.values[v])
        # ответ -
        return ans

    def find_max_path(self):
        self.dp = [-BIG for i in range(self.n)]
        return self.find_max_path_dfs(0, -1)


class DirectedGraph:
    def __init__(self, values):
        self.n = len(values)
        self.values = values
        self.edges = [[] for i in range(self.n)]
        self.counter = [0 for i in range(self.n)]

    def add_edge(self, u, v):
        u -= 1
        # Здесь добавляем одно ребро и увеличиваем counter вершины на 1 в ту, которую идем
        # Чтобы потом найти root
        v -= 1
        self.edges[u].append(v)
        self.counter[v] += 1

    def find_max_path_dfs(self, v):
        self.dp[v] = self.values[v]  # Изначально ставим значение самой вершины
        for child in self.edges[v]:  # Итерируемся по детям
            self.find_max_path_dfs(child)  # Запускаем рекурсию от ребенка
            self.dp[v] = max(self.dp[v],  # Обновляем наше значение dp[v]
                             max(0, self.dp[child]) + self.values[v])

    def find_root(self):
        for i in range(self.n):  # Находим вершину, в которую не ведет ни одно ребро
            if self.counter[i] == 0:
                return i

    def find_max_path(self):  # Ответом будем максимальное значение в dp[v]
        self.dp = [-BIG for i in range(self.n)]
        root = self.find_root()
        self.find_max_path_dfs(root)
        return max(self.dp)


def bidirected_graph_tests():
    graph = BidirectedGraph([1, 2, 3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 6

    graph = BidirectedGraph([1])
    assert graph.find_max_path() == 1

    graph = BidirectedGraph([-1, 2, 3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 4

    graph = BidirectedGraph([-1, 2, 3])
    graph.add_edge(2, 1)
    graph.add_edge(2, 3)
    assert graph.find_max_path() == 5

    graph = BidirectedGraph([1, 2, -3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 3

    graph = BidirectedGraph([-100, 2, 3, 5, 6])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(2, 4)
    graph.add_edge(2, 5)
    assert graph.find_max_path() == 13

    graph = BidirectedGraph([-100, 2, 20, 5, 6])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(2, 4)
    graph.add_edge(2, 5)
    assert graph.find_max_path() == 20

    print("bidirected successful")


def directed_graph_tests():
    graph = DirectedGraph([1, 2, 3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 4

    graph = DirectedGraph([1])
    assert graph.find_max_path() == 1

    graph = DirectedGraph([-1, 2, 3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 3

    graph = DirectedGraph([-1, 2, 3])
    graph.add_edge(2, 1)
    graph.add_edge(2, 3)
    assert graph.find_max_path() == 5

    graph = DirectedGraph([1, 2, -3])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    assert graph.find_max_path() == 3

    graph = DirectedGraph([-100, 2, 3, 5, 6])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(2, 4)
    graph.add_edge(2, 5)
    assert graph.find_max_path() == 8

    graph = DirectedGraph([-100, 2, 20, 5, 6])
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(2, 4)
    graph.add_edge(2, 5)
    assert graph.find_max_path() == 20

    print("directed successful")


bidirected_graph_tests()
directed_graph_tests()