树形 DP：没有上司的舞会

// 邻接表是怎么建起来的 —— 这一章自带的「存图」小节
//
// 树和图在代码里长什么样？这一章只需要最简单的那一种：
//
//     vector<vector<int>> son(n + 1);
//     son[k].push_back(l);        // k 是 l 的上司 → 把 l 挂到 k 的名下
//
// ★ 为什么不用二维数组 `int g[N][N]`：
//   n 个点的树只有 n-1 条边，而二维数组要开 n² 个格子。
//   n = 100000 时，邻接表存 10 万条边，二维数组要 100 亿个格子 —— 开都开不出来。
//   **稀疏的图用表，稠密的图才用矩阵。** 第 29 章会拿实测的内存和耗时把这件事说透，
//   这里够用就行。
//
// ⚠ 这一章的图有两个特殊之处，让它比一般的图好写：
//   ① 它是**树**，而且每条边都自带方向（上司 → 下属），所以只存单向就够了；
//      一般的无向图要 push_back 两次（第 29、30 章会讲）。
//   ② 根是「**没有上司的那个人**」，得数一下入度才知道 —— 不一定是 1 号。
//      wrongRoot.cpp 就是栽在这一句上的。
//
// 用法：./adj            （用正文那棵默认的 7 个点的树）
//       ./adj < 数据文件（格式同 brute.cpp）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    vector<long long> r;
    vector<pair<int, int>> edges;
    if (cin >> n && n > 0) {
        r.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) cin >> r[i];
        for (int i = 0; i < n - 1; i++) {
            int l, k;
            if (!(cin >> l >> k)) break;
            edges.push_back({l, k});
        }
    } else {
        n = 7;
        r = {0, 1, 3, -5, -1, 2, 5, 7};
        edges = {{1, 5}, {2, 6}, {3, 4}, {4, 1}, {6, 5}, {7, 5}};
    }

    vector<vector<int>> son(n + 1);
    vector<int> hasBoss(n + 1, 0);
    for (auto [l, k] : edges) {
        son[k].push_back(l);                     // ← 建表就这一行
        hasBoss[l] = 1;
    }

    cout << "读进来的 " << edges.size() << " 条「l k = k 是 l 的上司」：\n  ";
    for (auto [l, k] : edges) cout << k << "→" << l << "  ";
    cout << "\n\n建好的邻接表 son[u]（u 的直接下属）：\n";
    for (int u = 1; u <= n; u++) {
        cout << "  son[" << u << "] = {";
        for (size_t i = 0; i < son[u].size(); i++) cout << (i ? ", " : "") << son[u][i];
        cout << "}";
        if (son[u].empty()) cout << "        <- 叶子，没有下属";
        cout << "\n";
    }

    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }
    cout << "\n没有上司的那个人 = " << root << " 号，它就是根。\n";
    cout << "★ 注意它不是 1 号 —— 这一章有一整个错误版本（wrongRoot.cpp）就栽在这里。\n";

    long long cells = (long long)(n + 1) * (n + 1);
    cout << "\n顺带算笔账：这棵树 " << n << " 个点、" << edges.size() << " 条边。\n";
    cout << "  邻接表存了 " << edges.size() << " 个数；";
    cout << "换成二维数组 g[" << n + 1 << "][" << n + 1 << "] 要 " << cells << " 个格子。\n";
    cout << "  点数一大，这个差距就是「开得出来」和「开不出来」的差别（第 29 章细算）。\n";
    return 0;
}

// 没有上司的舞会 —— 暴力：2ⁿ 枚举「每个人来不来」，再检查有没有直接上下级同时到场
//
// ★ 它是**完全不同的思路**（第 20 章那条规矩）：
//   这份代码里**没有树、没有 DFS、没有状态、没有回溯** ——
//   它甚至不需要知道谁是根，只是把 n 个人的「来 / 不来」全排一遍，
//   然后逐条边检查一下合不合法。
//   正解那边是「在树上一层层往上归」—— 两边连数据结构都不一样，对上了才有说服力。
//
// 复杂度 O(2ⁿ × n)：n = 24 是一千七百万种名单，n = 30 是十亿多种 —— 正文第 10 步会实测。
//
// ⚠ 常数很小，因为「逐条边检查」通常在第一条边就 break 了（随机一份名单，
//   多半一上来就有一对上下级同时到场）。但**枚举本身还是实打实的 2ⁿ 次** ——
//   省下的是每次检查的时间，省不掉要检查多少次。
//   （第 25 章那条教训：要拿暴力证明「有多慢」，先确认它真的走完了。这里确实走完了。）
//
// 题意：n 个职员组成一棵树（上下级关系），第 i 个人的快乐指数是 r[i]。
//       **如果某人的直接上司到场，他就不来**。求到场的人快乐指数之和的最大值。
// 输入：第一行 n
//       第二行 n 个整数 r[1..n]（可以是负数）
//       接下来 n-1 行，每行两个数 l k，表示 **k 是 l 的直接上司**
// 输出：最大快乐指数之和
//
// ⚠ 一个人都不来是允许的，所以答案至少是 0（全是负数时就该谁都不来）。
// ⚠ 洛谷 P1352 的输入多一行 `0 0` 结尾，读入时忽略掉就一样了。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    // ⚠ `1 << n` 是 int 移位，n ≥ 31 就是未定义行为（而且那时候它也早就跑不完了）
    if (n > 30) { cerr << "n 太大了，2ⁿ 暴力只支持 n <= 30\n"; return 1; }
    vector<long long> r(n + 1);
    for (int i = 1; i <= n; i++) cin >> r[i];

    vector<pair<int, int>> edge;                 // (下属, 上司)
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        edge.push_back({l, k});
    }

    long long best = 0;                          // 一个都不选，和为 0
    for (int s = 0; s < (1 << n); s++) {
        bool ok = true;
        for (auto [l, k] : edge)                 // 上司和下属不能同时到场
            if ((s >> (l - 1) & 1) && (s >> (k - 1) & 1)) { ok = false; break; }
        if (!ok) continue;
        long long sum = 0;
        for (int i = 1; i <= n; i++)
            if (s >> (i - 1) & 1) sum += r[i];
        best = max(best, sum);
    }

    cout << best << "\n";
    return 0;
}

// 没有上司的舞会 —— 正解：树形 DP，★ 转移在 DFS **回溯**的时候做
//
// 状态比前面几章多的那一维，是「**当前这个点自己选不选**」：
//
//     f[u][0] = 以 u 为根的子树里，u **不来**时的最大快乐和
//     f[u][1] = 以 u 为根的子树里，u **来**  时的最大快乐和
//
// 转移（v 是 u 的儿子）：
//
//     f[u][0] = Σ max(f[v][0], f[v][1])      u 不来 → 儿子来不来都行，各自取更大的
//     f[u][1] = r[u] + Σ f[v][0]             u 来   → 儿子一个都不能来
//
// 答案 = max(f[root][0], f[root][1])。
//
// ★ 关键一步：**这两个 Σ 必须在儿子全部算完之后才能加** —— 也就是在递归返回之后。
//   「依赖谁，就先填谁」（第 21 章）第五次登场，而这一次它有个现成的名字：**后序遍历**。
//   你在第 1 章就写过它了（那时候叫「归」），第 11 章归并排序、
//   第 26 章输出合并方案，用的都是同一件东西。
//
//   把累加写在递归**前面**（wrongPre.cpp）会怎样？儿子的 f 还全是 0，
//   于是每个点都只看见自己 —— 不报错、不崩溃，安静地给你一个偏小的答案。
//   这和第 26 章「左端点正序读到还没算好的格子」是同一个病。
//
// 复杂度 O(n)：每条边只在回溯时被用一次。空间 O(n)。
// 输入输出同 brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> r;
vector<vector<int>> son;                         // 邻接表：son[u] = u 的所有直接下属
vector<array<long long, 2>> f;

// ⚠ 这里用递归 DFS。n 很大（比如一条 10 万个点的链）时会爆栈，
//   正文第 12 步会实测这个边界 —— 那是第 21 章 stairsDeep.cpp 那个坑的树上版本。
void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);                                  // ★ 先把儿子整棵子树算完
        f[u][0] += max(f[v][0], f[v][1]);        // ★ 回来之后才累加 —— 后序
        f[u][1] += f[v][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        son[k].push_back(l);                     // k 是 l 的上司 → l 挂在 k 下面
        hasBoss[l] = 1;
    }

    // ⚠ 根是「没有上司的那个人」，**不一定是 1 号**。
    //   直接从 1 开始 DFS 是这一章最容易犯又最容易蒙混过关的错（wrongRoot.cpp），
    //   因为很多人造的数据里 1 恰好就是根。
    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);

    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}

// 把 DFS 的**回溯顺序**和每个点的 f[u][0] / f[u][1] 打出来 —— 动画就是照着这个次序播的
//
// 为什么要有它：动画是用 TypeScript 把这个算法重写一遍画出来的。
// 只比最后那个答案是不够的 —— 答案蒙对、中间过程画错，学生一样看不出来。
// 所以这里把**每个点被算完的次序**和它的两个 f 值都打出来，
// check:viz 拿它和动画的每一帧逐个对照。（第 23、26 章的 trace.cpp 是同样的用意。）
//
// ★ 这张表本身就是这一章的 ★ 的样子：
//   **每个点都排在它所有儿子的后面。** 那就是后序遍历，也就是「依赖谁，就先填谁」。
//
// 用法：./trace            （用正文那棵默认的 7 个点的树）
//       ./trace < 数据文件（格式同 brute.cpp）

#include <bits/stdc++.h>
using namespace std;

int n, root;
vector<long long> r;
vector<vector<int>> son;
vector<array<long long, 2>> f;
vector<int> order, depth;

void dfs(int u, int d) {
    depth[u] = d;
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v, d + 1);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
    order.push_back(u);                          // ★ 儿子都归位了，才轮到自己
}

int main() {
    // ⚠ cout 和 printf 混用（表格用 printf 好对齐），所以不能关 ios::sync_with_stdio
    vector<pair<int, int>> edges;
    if (cin >> n && n > 0) {
        r.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) cin >> r[i];
        for (int i = 0; i < n - 1; i++) {
            int l, k;
            if (!(cin >> l >> k)) break;
            edges.push_back({l, k});
        }
    } else {
        n = 7;                                   // 正文那棵默认的树
        r = {0, 1, 3, -5, -1, 2, 5, 7};
        edges = {{1, 5}, {2, 6}, {3, 4}, {4, 1}, {6, 5}, {7, 5}};
    }

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (auto [l, k] : edges) { son[k].push_back(l); hasBoss[l] = 1; }
    root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    depth.assign(n + 1, 0);
    dfs(root, 0);

    cout << "根是 " << root << " 号（没有上司的那个人，不一定是 1 号）\n\n";
    cout << "  次序   点   深度   快乐   f[u][0] 不来   f[u][1] 来   子树最好   儿子\n";
    cout << "  ----   --   ----   ----   ------------   ----------   --------   ----------\n";

    for (size_t t = 0; t < order.size(); t++) {
        int u = order[t];
        string kids;
        for (int v : son[u]) kids += (kids.empty() ? "" : " ") + to_string(v);
        if (kids.empty()) kids = "-";
        printf("  %4zu   %2d   %4d   %4lld   %12lld   %10lld   %8lld   %s\n",
               t + 1, u, depth[u], r[u], f[u][0], f[u][1], max(f[u][0], f[u][1]), kids.c_str());
    }

    cout << "\n答案 max(f[" << root << "][0], f[" << root << "][1]) = max("
         << f[root][0] << ", " << f[root][1] << ") = " << max(f[root][0], f[root][1]) << "\n";
    cout << "每个点都排在它所有儿子的后面 —— 这就是「后序」，也就是这一章的全部内容。\n";
    return 0;
}

// ✗ 错误版本二：u 来的时候，还允许儿子也来 —— 把题目的那条限制整个写没了
//
//     正确： f[u][1] = r[u] + Σ f[v][0]                  儿子一个都不能来
//     错误： f[u][1] = r[u] + Σ max(f[v][0], f[v][1])    儿子随便
//
// 这样一来「直接上司到场，下属就不来」这条唯一的限制就不存在了，
// 于是它解的是另一道题：**把所有快乐指数为正的人全叫来**。
//
// ★ 这又是「写错了就是另一道题」那个系列（第 23~26 章一共六条恒等式）。
//   正文第 12 步用 300 组数据钉死了这一条：
//   它的输出恒等于 Σ max(0, r[i]) —— 一组不差。
//
// ⚠ 注意它是**偏大**的那一类错误（限制少了，答案只会更大）。
//   偏大的错误没法用眼力认出来 —— 一个偏大的答案和一个「数据比较难」的正确答案长得一样。
//
// 输入输出同 brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> r;
vector<vector<int>> son;
vector<array<long long, 2>> f;

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += max(f[v][0], f[v][1]);        // ✗ 应该是 f[v][0]
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        son[k].push_back(l);
        hasBoss[l] = 1;
    }
    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);
    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}

// ✗ 错误版本三：以为「上司不来，下属就必须来」—— 这一章最像回事的一个误解
//
//     正确： f[u][0] = Σ max(f[v][0], f[v][1])    u 不来 → 儿子来不来都行
//     错误： f[u][0] = Σ f[v][1]                  u 不来 → 儿子必须来
//
// 题目说的是「**上司来了，下属就不来**」，它**没有**反过来说
// 「上司不来，下属就必须来」。这是一个纯粹的读题错误，和算法一点关系都没有。
//
// ★ 它最值得讲的地方是：**快乐指数全是正数时，它经常恰好是对的。**
//   因为「能来就来」本来就划算 —— 正确写法给儿子取 max(f[v][0], f[v][1])，
//   而值全为正时那个 max 十有八九就是 f[v][1]，和错误写法取的是同一个。
//
//   实测（300 组固定种子，见正文第 12 步那张表）：
//       生成器只造正数        → 抓住 195 / 300
//       生成器带上负数        → 抓住 268 / 300
//
//   所以对拍数据**必须有负数**。这正是第 20 章那条规矩：
//   **让「错误的直觉」在你的数据上必定失败** ——
//   要抓「以为下属必须来」，就得造出「这个下属来了反而亏」的局面。
//
// 输入输出同 brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> r;
vector<vector<int>> son;
vector<array<long long, 2>> f;

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += f[v][1];                      // ✗ 应该是 max(f[v][0], f[v][1])
        f[u][1] += f[v][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        son[k].push_back(l);
        hasBoss[l] = 1;
    }
    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);
    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}

// ✗ 错误版本五：最后输出 f[root][1]，忘了和 f[root][0] 取 max
//
// 整棵树都算对了，只在最后一行栽了 —— 它默认「根一定要来」。
//
// ★ 这个 bug 只在**根不来更划算**的时候才现形。
//   而只要快乐指数全是正数，根来一趟总不亏，它就一直是对的 ——
//   所以生成器**必须造负数**（尤其是根的快乐指数为负的局面）。
//
//   第 20 章那条规矩的又一次应用：
//   **让「错误的直觉」在你的数据上必定失败** ——
//   要抓「忘了取 max」，就必须造出「根宁可不来」的数据。
//
// ⚠ 顺带说一句：题目允许一个人都不来（答案至少是 0），
//   这份代码连这一点也丢了 —— 全是负数时它会输出一个负数。
//
// 输入输出同 brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> r;
vector<vector<int>> son;
vector<array<long long, 2>> f;

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        son[k].push_back(l);
        hasBoss[l] = 1;
    }
    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);
    cout << f[root][1] << "\n";                  // ✗ 应该是 max(f[root][0], f[root][1])
    return 0;
}

// 输出**到底哪些人来了** —— 第 26 章那套回溯，在树上再用一次
//
// 第 23 章说过「要方案就得开二维表」，第 26 章用 from[l][r] 还了这笔账。
// 树形 DP 这里更省事：f[u][0] / f[u][1] 本来就分开存着，
// **回溯的时候只要问一句「这个点当初取的是哪一个状态」**，答案自己就出来了。
//
//   从根开始：取 f[root][0] 和 f[root][1] 里更大的那个；
//   · 如果这个点**来**了 → 它的儿子一个都不能来，全部按「不来」往下走；
//   · 如果这个点**没来** → 每个儿子各自取更大的那个状态，各走各的。
//
// ⚠ 和第 26 章不同的是，这次回溯是**前序**的（先定自己，再定儿子）——
//   因为「儿子能不能来」取决于「我来没来」。
//   算 f 的时候是后序（要先知道儿子），回溯方案的时候是前序（要先知道自己）。
//   **同一棵树，两个方向，各有各的理由** —— 这是这一节最值得带走的一句话。
//
// 用法：./path            （用正文那棵默认的 7 个点的树）
//       ./path < 数据文件（格式同 brute.cpp）
//
// check:viz 对这份输出做的是**硬验证**：名单里不能有任何一对直接上下级，
// 快乐指数之和必须正好等于第一行那个答案。

#include <bits/stdc++.h>
using namespace std;

int n, root;
vector<long long> r;
vector<vector<int>> son;
vector<array<long long, 2>> f;
vector<int> come;

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

// take = 这个点来不来（回溯是前序：先定自己，再定儿子）
void back(int u, int take) {
    come[u] = take;
    for (int v : son[u]) {
        if (take) back(v, 0);                            // 我来了 → 儿子一个都不能来
        else back(v, f[v][1] > f[v][0] ? 1 : 0);         // 我没来 → 儿子各自挑更好的
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<pair<int, int>> edges;
    if (cin >> n && n > 0) {
        r.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) cin >> r[i];
        for (int i = 0; i < n - 1; i++) {
            int l, k;
            if (!(cin >> l >> k)) break;
            edges.push_back({l, k});
        }
    } else {
        n = 7;
        r = {0, 1, 3, -5, -1, 2, 5, 7};
        edges = {{1, 5}, {2, 6}, {3, 4}, {4, 1}, {6, 5}, {7, 5}};
    }

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (auto [l, k] : edges) { son[k].push_back(l); hasBoss[l] = 1; }
    root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);
    long long best = max(f[root][0], f[root][1]);

    come.assign(n + 1, 0);
    back(root, f[root][1] > f[root][0] ? 1 : 0);

    cout << "最大快乐指数之和 = " << best << "\n\n";

    cout << "到场名单：";
    long long sum = 0;
    bool any = false;
    for (int i = 1; i <= n; i++)
        if (come[i]) { cout << (any ? " " : "") << i; sum += r[i]; any = true; }
    if (!any) cout << "（一个人都不来）";
    cout << "\n快乐指数：";
    any = false;
    for (int i = 1; i <= n; i++)
        if (come[i]) { cout << (any ? " + " : "") << r[i]; any = true; }
    cout << (any ? " = " : "0 = ") << sum << "\n\n";

    cout << "逐个点看（★ 每一对直接上下级里，最多只有一个「来」）：\n";
    for (int i = 1; i <= n; i++) {
        cout << "  " << i << " 号（快乐 " << r[i] << "）："
             << (come[i] ? "来" : "不来");
        for (int v : son[i])
            cout << (v == son[i][0] ? "，下属 " : " ") << v << (come[v] ? "(来)" : "(不来)");
        cout << "\n";
    }
    return 0;
}

// 没有上司的舞会 —— 正解：树形 DP，★ 转移在 DFS **回溯**的时候做
//
// 状态比前面几章多的那一维，是「**当前这个点自己选不选**」：
//
//     f[u][0] = 以 u 为根的子树里，u **不来**时的最大快乐和
//     f[u][1] = 以 u 为根的子树里，u **来**  时的最大快乐和
//
// 转移（v 是 u 的儿子）：
//
//     f[u][0] = Σ max(f[v][0], f[v][1])      u 不来 → 儿子来不来都行，各自取更大的
//     f[u][1] = r[u] + Σ f[v][0]             u 来   → 儿子一个都不能来
//
// 答案 = max(f[root][0], f[root][1])。
//
// ★ 关键一步：**这两个 Σ 必须在儿子全部算完之后才能加** —— 也就是在递归返回之后。
//   「依赖谁，就先填谁」（第 21 章）第五次登场，而这一次它有个现成的名字：**后序遍历**。
//   你在第 1 章就写过它了（那时候叫「归」），第 11 章归并排序、
//   第 26 章输出合并方案，用的都是同一件东西。
//
//   把累加写在递归**前面**（wrongPre.cpp）会怎样？儿子的 f 还全是 0，
//   于是每个点都只看见自己 —— 不报错、不崩溃，安静地给你一个偏小的答案。
//   这和第 26 章「左端点正序读到还没算好的格子」是同一个病。
//
// 复杂度 O(n)：每条边只在回溯时被用一次。空间 O(n)。
// 输入输出同 brute.cpp。

#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> r;
vector<vector<int>> son;                         // 邻接表：son[u] = u 的所有直接下属
vector<array<long long, 2>> f;

// ⚠ 这里用递归 DFS。n 很大（比如一条 10 万个点的链）时会爆栈，
//   正文第 12 步会实测这个边界 —— 那是第 21 章 stairsDeep.cpp 那个坑的树上版本。
void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);                                  // ★ 先把儿子整棵子树算完
        f[u][0] += max(f[v][0], f[v][1]);        // ★ 回来之后才累加 —— 后序
        f[u][1] += f[v][0];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n) || n <= 0) return 0;
    r.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> r[i];

    son.assign(n + 1, {});
    vector<int> hasBoss(n + 1, 0);
    for (int i = 0; i < n - 1; i++) {
        int l, k;
        if (!(cin >> l >> k)) break;
        son[k].push_back(l);                     // k 是 l 的上司 → l 挂在 k 下面
        hasBoss[l] = 1;
    }

    // ⚠ 根是「没有上司的那个人」，**不一定是 1 号**。
    //   直接从 1 开始 DFS 是这一章最容易犯又最容易蒙混过关的错（wrongRoot.cpp），
    //   因为很多人造的数据里 1 恰好就是根。
    int root = 1;
    for (int i = 1; i <= n; i++) if (!hasBoss[i]) { root = i; break; }

    f.assign(n + 1, {0, 0});
    dfs(root);

    cout << max(f[root][0], f[root][1]) << "\n";
    return 0;
}