// Задача очень похожа на задачу о максимальном независимом множестве. Тогда она решается следующим
// образом, для данного корня дерева максимальная сумма будет достигаться либо когда мы берем текущий корень
// и его "внуков" или мы не берем текущий корень, а берем "сыновей". Эту задачу решает класс task118_1.
// С другой стороны, в условии не сказано что множество должно быть максимальным по включению и кроме того веса
// узлов могут быть отрицательными. Это навидит на мысль, что узел можно не надо брать если его вес < 0. Это
// решается классе task118_2 (есть одно "но", на выходе может получиться пустое множество). Если это недопустимо
// то случай всех отрицательных весов можно рассмотреть отдельно (task118_3). Короче, мораль следующая - надо или
// более аккуратно формулировать задачу или давать больше примеров:-) Да, дерево считаем n-арным

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;


class task118
{
protected:
    const vector<int>& Values;
    vector<int>  Results;
    const unsigned long N;
    vector<vector<int>> Tree;

private:

    vector<vector<int>> build_tree(const vector<pair<int,int>>& edges)
    {
        vector<vector<int>> result(N, vector<int>());

        for (const auto& p : edges) {
            result[p.first-1].push_back(p.second-1);
            result[p.second-1].push_back(p.first-1);
        }

        return result;
    }

protected:

    virtual int walk(int node, int parent) = 0;

public:

    task118(const vector<int>& values, const vector<pair<int,int>>& edges)
        : Values(values)
        , Results(values.size(), numeric_limits<int>::min())
        , N(values.size())
    {
        Tree = build_tree(edges);
    }

    virtual int solve()
    {
        return walk(0,-1);
    }
};

class task118_1 : public task118
{
    using task118::task118;
protected:
    int walk(int node, int parent) override
    {

        if (Results[node] != numeric_limits<int>::min()) {
            return Results[node];
        }

        int sons_sum = 0;

        for (int child_idx = 0; child_idx < Tree[node].size(); ++child_idx) {
            auto son = Tree[node][child_idx];
            if (son != parent) {
                sons_sum += walk(son, node);
            }
        }

        int grandsons_sum = 0;

        for (int child_idx = 0; child_idx < Tree[node].size(); ++child_idx) {
            auto son = Tree[node][child_idx];
            if (son != parent) {
                for (int child_idx = 0; child_idx < Tree[son].size(); ++child_idx) {
                    auto grand_son = Tree[son][child_idx];
                    if (grand_son != node) {
                        grandsons_sum += walk(grand_son, son);
                    }
                }
            }
        }

        Results[node] = max(0, max(sons_sum,Values[node] + grandsons_sum));
        return Results[node];
    }
};

class task118_2 : public task118
{
    using task118::task118;
protected:
    int walk(int node, int parent) override
    {

        if (Results[node] != numeric_limits<int>::min()) {
            return Results[node];
        }

        int sons_sum = 0;

        for (int child_idx = 0; child_idx < Tree[node].size(); ++child_idx) {
            auto son = Tree[node][child_idx];
            if (son != parent) {
                sons_sum += walk(son, node);
            }
        }

        int grandsons_sum = 0;

        for (int child_idx = 0; child_idx < Tree[node].size(); ++child_idx) {
            auto son = Tree[node][child_idx];
            if (son != parent) {
                for (int child_idx = 0; child_idx < Tree[son].size(); ++child_idx) {
                    auto grand_son = Tree[son][child_idx];
                    if (grand_son != node) {
                        grandsons_sum += walk(grand_son, son);
                    }
                }
            }
        }

        Results[node] = max(0, max(sons_sum,max(0, Values[node]) + grandsons_sum));
        return Results[node];
    }
};

class task118_3 : public task118_1
{
public:
    int solve() override
    {
        auto neg = std::all_of(Values.begin(), Values.end(), [](int x) { return x < 0;});
        if (neg) {
            return *std::max_element(Values.begin(), Values.end());
        }
        return walk(0,-1);
    }
};