/*
QUESTION 12: Media.Net OA — Choosing the Most Valuable Tree Root

Problem Statement:
You are given a tree.
Each node contains a candy value.

If you choose some node as the root, then every root-to-leaf path has a path sum.

For that chosen root:
best = maximum root-to-leaf path sum
worst = minimum root-to-leaf path sum

The value of the root is:
best - worst

Return the maximum value among all possible roots.

Hard Constraints:
1 <= N <= 200000
1 <= candy[i] <= 1e9

Example:
candies = [6, 2, 9, 1]
edges:
1 - 2
2 - 3
2 - 4

Expected Output:
8

Explanation:
If node 2 is chosen as root:
paths are:
2 -> 1 = 8
2 -> 3 = 11
2 -> 4 = 3

best - worst = 11 - 3 = 8

Brute Force:
For every node:
- Treat it as root.
- DFS to all leaves.
- Find max and min root-to-leaf path sums.

Time Complexity:
O(N^2)

Optimized Approach:
Use rerooting DP.

For each directed side of an edge, compute the best and worst path from that side
to a leaf in that component.

Then every node can combine values from all neighboring directions.

Time Complexity:
O(N)

Space Complexity:
O(N)
*/

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

class Solution {
public:
    using ll = long long;

    const ll NEG = -(1LL << 60);
    const ll POS =  (1LL << 60);

    int n;
    vector<vector<int>> g;
    vector<ll> val;

    vector<ll> downMax, downMin;
    ll answer = 0;

    void dfsDown(int u, int p) {
        downMax[u] = NEG;
        downMin[u] = POS;

        bool hasChild = false;

        for (int v : g[u]) {
            if (v == p) continue;

            hasChild = true;
            dfsDown(v, u);

            downMax[u] = max(downMax[u], val[u] + downMax[v]);
            downMin[u] = min(downMin[u], val[u] + downMin[v]);
        }

        if (!hasChild) {
            downMax[u] = val[u];
            downMin[u] = val[u];
        }
    }

    void dfsReroot(int u, int p, ll fromParentMax, ll fromParentMin) {
        vector<pair<ll, int>> maxCand;
        vector<pair<ll, int>> minCand;

        if (fromParentMax != NEG) {
            maxCand.push_back({fromParentMax, p});
            minCand.push_back({fromParentMin, p});
        }

        for (int v : g[u]) {
            if (v == p) continue;

            maxCand.push_back({downMax[v], v});
            minCand.push_back({downMin[v], v});
        }

        if (!maxCand.empty()) {
            ll rootMax = val[u] + max_element(maxCand.begin(), maxCand.end())->first;
            ll rootMin = val[u] + min_element(minCand.begin(), minCand.end())->first;

            answer = max(answer, rootMax - rootMin);
        }

        for (int v : g[u]) {
            if (v == p) continue;

            ll bestMax = NEG;
            ll bestMin = POS;

            for (auto [x, id] : maxCand) {
                if (id != v) bestMax = max(bestMax, x);
            }

            for (auto [x, id] : minCand) {
                if (id != v) bestMin = min(bestMin, x);
            }

            ll passMax = (bestMax == NEG ? val[u] : val[u] + bestMax);
            ll passMin = (bestMin == POS ? val[u] : val[u] + bestMin);

            dfsReroot(v, u, passMax, passMin);
        }
    }

    long long bestRootValue(vector<int>& candies, vector<vector<int>>& edges) {
        n = candies.size();

        if (n == 1) return 0;

        val.assign(n, 0);

        for (int i = 0; i < n; i++) {
            val[i] = candies[i];
        }

        g.assign(n, {});

        for (auto &e : edges) {
            int u = e[0] - 1;
            int v = e[1] - 1;

            g[u].push_back(v);
            g[v].push_back(u);
        }

        downMax.assign(n, NEG);
        downMin.assign(n, POS);

        dfsDown(0, -1);
        dfsReroot(0, -1, NEG, POS);

        return answer;
    }
};

int main() {
    Solution sol;

    vector<int> candies = {6, 2, 9, 1};

    vector<vector<int>> edges = {
        {1, 2},
        {2, 3},
        {2, 4}
    };

    cout << sol.bestRootValue(candies, edges) << endl;

    return 0;
}