令 $u>v$ ，$f(u, v)=max(A_u, A_v) \times |A_u-A_v| = A_u^2 - A_u \times A_v$ ，$A_u \times A_v$ 考虑用 $(\sum_{u\in subtree(i)}A_u)^2$ 维护。

考虑树上启发式合并，使用树状数组维护 ${A_u}^2$ 。一个点权 $A_i$ ，对于大于等于 $A_i$ 的点权显然应该加上 $rangesum(A_i, MAXN) \times 2$ ，对于小于 $A_i$ 的点权应该加上 $count(A_i - 1) \times {A_i}^2 \times 2$ ，所以还要用一个树状数组维护 $count$ 。

有个细节，任何一个点自身与自身是没有贡献的，上述计算贡献时（$\times 2$），那么你先 ($-A_i^2$)，后面（$-sum^2$）时就不重不漏了。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

template <class T>
struct Fenwick {
    const int N;
    std::vector<T> f;
    Fenwick(int _) : N(_), f(_ + 10) {}

    void add(int x, T v) {
        for (int i = x; i <= N; i += (i bitand -i)) {
            f[i] += v;
        }
    }

    T query(int x) {
        if (x > N or x <= 0) {
            return T(0);
        }

        T res = 0;
        for (int i = x; i; i -= (i bitand -i)) {
            res += f[i];
        }
        return res;
    }

    T rangesum(int l, int r) {
        if (l > r) {
            return T(0);
        }

        return query(r) - query(l - 1);
    }
};

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

    int n;
    std::cin >> n;

    std::vector<int> e[n + 1];
    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    std::vector<u64> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    int DFN = 0;
    std::vector<int> sz(n + 1, 1), son(n + 1), L(n + 1), R(n + 1), ord(n + 1);
    std::vector<u64> sum(n + 1);
    std::function<void(int, int)> dfs = [&](int u, int F) -> void {
        L[u] = ++DFN;
        ord[DFN] = u;
        sum[u] = a[u];
        for (auto v : e[u]) {
            if (v not_eq F) {
                dfs(v, u);
                sz[u] += sz[v];
                sum[u] += sum[v];
                if (not son[u] or sz[v] > sz[son[u]]) {
                    son[u] = v;
                }
            }
        }
        R[u] = DFN;
    };
    dfs(1, -1);

    Fenwick<u64> fen(1E6 + 1), fen1(1E6 + 1);

    std::vector<u64> res(n + 1);
    std::function<void(int, int)> solve = [&](int u, int F) -> void {
        for (auto v : e[u]) {
            if (v not_eq F and v not_eq son[u]) {
                solve(v, u);
                for (int i = L[v]; i <= R[v]; ++i) {
                    int V = ord[i];
                    fen.add(a[V], -a[V] * a[V]);
                    fen1.add(a[V], -1);
                }
            }
        }
        if (son[u]) {
            solve(son[u], u);
            res[u] += res[son[u]];
        }

        for (auto v : e[u]) {
            if (v not_eq F and v not_eq son[u]) {
                for (int i = L[v]; i <= R[v]; ++i) {
                    int V = ord[i];
                    fen.add(a[V], a[V] * a[V]);
                    fen1.add(a[V], 1);
                    res[u] += fen.rangesum(a[V] + 1, 1E6) * 2;
                    res[u] += fen1.rangesum(1, a[V]) * a[V] * a[V] * 2;
                    res[u] -= a[V] * a[V];
                }
            }
        }
        fen.add(a[u], a[u] * a[u]);
        fen1.add(a[u], 1);
        res[u] += fen.rangesum(a[u] + 1, 1E6) * 2;
        res[u] += fen1.rangesum(1, a[u]) * a[u] * a[u] * 2;
        res[u] -= a[u] * a[u];
    };
    solve(1, -1);

    u64 ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans xor_eq res[i] - sum[i] * sum[i];
    }
    std::cout << ans << "\n";

    return 0;
}