Observation 1: the path minimum is the LCA value

Let $$$x=\operatorname{LCA}(u,v)$$$.

Because the values strictly increase from parent to child, every vertex below $$$x$$$ has a value larger than $$$P_x$$$. Therefore

So we only need to reason about LCA values.

Observation 2: score of the original tree

Let $$$T_v$$$ be the subtree of $$$v$$$ and

Define

and, for $$$v\ne r$$$,

For any pair $$$u,v$$$,

The term $$$w_x$$$ is present exactly when both endpoints belong to $$$T_x$$$.

There are $$$\binom{s_x}{2}$$$ such pairs, hence

This can be computed in $$$O(N)$$$.

Observation 3: loss of one cut

Consider cutting the edge between a non-root vertex $$$v$$$ and its parent.

Define

For every fixed vertex in $$$T_v$$$, its total contribution with all vertices outside $$$T_v$$$ is exactly $$$H_v$$$.

Since there are $$$s_v$$$ vertices in $$$T_v$$$, the loss is

We can compute all $$$H_v$$$ using

Let

Then define the line

The reason for this definition becomes clear when considering two cuts.

Observation 4: two nested cuts

Suppose $$$a$$$ is an ancestor of $$$b$$$.

The two individual losses count some pairs twice.

A pair belongs to both losses exactly when one endpoint is inside $$$T_b$$$ and the other is outside $$$T_a$$$.

Therefore the overlap is

Hence

Since $$$X_b=s_b$$$,

So if $$$a$$$ is fixed, we need the minimum value of all descendant lines at

This is a standard Li Chao tree query.

Observation 5: two disjoint cuts

Now suppose $$$T_a$$$ and $$$T_b$$$ are disjoint.

Let

A pair is counted in both individual losses exactly when one endpoint is in $$$T_a$$$ and the other is in $$$T_b$$$.

Every such pair has bottleneck $$$P_x$$$, and there are

such pairs.

Therefore the overlap is

Thus

For fixed $$$a$$$,

Again this is exactly our line

queried at

So both possible configurations of the two cuts have become minimum line queries.

Observation 6: small-to-large merging

Process the rooted tree bottom-up.

For each processed subtree, maintain:

• the list of cut vertices whose edges are available in this subtree;
• a Li Chao tree containing their lines.

At vertex $$$x$$$, choose the largest child structure as the base.

For every other child $$$c$$$, iterate through all lines belonging to $$$c$$$.

For a line belonging to $$$a$$$, the other cut belongs to the already merged part. Since $$$a$$$ and the other cut lie in different child-subtrees of $$$x$$$, their LCA is exactly $$$x$$$.

Therefore query the base at

If the minimum line value is $$$m$$$, then the corresponding two-cut loss is

After querying all lines of the smaller structure, insert them into the base structure.

After all children have been merged, the base contains all cuts strictly below $$$x$$$.

If $$$x\ne r$$$, we can pair the edge above $$$x$$$ with any descendant edge. For that case the required query is

Therefore query the base at $$$H_x$$$ and add $$$Y_x$$$.

Finally, insert the line corresponding to the edge above $$$x$$$ so that ancestors can use it.

Because we always merge the smaller structure into the larger one, every line is moved at most $$$O(\log N)$$$ times.

Each Li Chao insertion/query takes $$$O(\log N)$$$, giving

time.

Implementation detail

The query coordinate can be as large as

Therefore the Li Chao domain is $$$[0,N^2+1]$$$.

We must not represent the Li Chao tree using heap-style indices inside a dense vector. A depth of $$$O(\log N)$$$ can then produce node indices of size $$$O(N^2)$$$.

Instead, use an explicit node pool:

struct LiChaoNode {
    int line = -1;
    int left = -1;
    int right = -1;
};

Only nodes that are actually created are stored.

The tree traversal should also be iterative because the input tree may be a path of length $$$2\cdot10^5$$$.

Correctness

Every pair of cuts is classified exactly once.

If one cut is an ancestor of the other, it is considered when the ancestor vertex is processed.

Otherwise, let $$$x$$$ be the LCA of the two cut vertices. They belong to different child-subtrees of $$$x$$$, so the pair is considered when those child structures are merged at $$$x$$$.

For every considered pair, the formulas above give its exact loss by inclusion-exclusion.

Therefore the algorithm finds

The final answer is

Complexity

There are $$$O(N)$$$ possible cut edges.

Small-to-large merging moves each line only $$$O(\log N)$$$ times, and each Li Chao insertion/query costs $$$O(\log N)$$$.

Therefore:

time and

memory.

// Assisted by an LLM
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static constexpr ll INF = (1LL << 62);
struct Line {
    ll m = 0, b = 0;
    ll get(ll x) const {
        return m * x + b;
    }
};
struct LiChaoNode {
    int line = -1;
    int left = -1;
    int right = -1;
};
class LiChao {
    ll L, R;
    const vector<Line>* lines;
    vector<LiChaoNode> tree;
    int root = -1;
    int newNode() {
        tree.push_back({});
        return (int)tree.size() - 1;
    }
    int addRec(int node, ll l, ll r, int id) {
        if (node == -1) {
            node = newNode();
            tree[node].line = id;
            return node;
        }
        ll mid = l + (r - l) / 2;
        int cur = tree[node].line;
        if ((*lines)[id].get(mid) < (*lines)[cur].get(mid)) {
            swap(tree[node].line, id);
            cur = tree[node].line;
        }
        if (l == r)
            return node;
        if ((*lines)[id].get(l) <
            (*lines)[tree[node].line].get(l)) {
            tree[node].left =
                addRec(tree[node].left, l, mid, id);
        } else {
            tree[node].right =
                addRec(tree[node].right, mid + 1, r, id);
        }
        return node;
    }
    ll queryRec(int node, ll l, ll r, ll x) const {
        if (node == -1)
            return INF;
        ll ans = (*lines)[tree[node].line].get(x);
        if (l == r)
            return ans;
        ll mid = l + (r - l) / 2;
        if (x <= mid) {
            ans = min(ans,
                      queryRec(tree[node].left,
                               l, mid, x));
        } else {
            ans = min(ans,
                      queryRec(tree[node].right,
                               mid + 1, r, x));
        }
        return ans;
    }
public:
    LiChao() = default;
    LiChao(ll L_, ll R_, const vector<Line>* lines_)
        : L(L_), R(R_), lines(lines_) {}
    void add(int id) {
        root = addRec(root, L, R, id);
    }
    ll query(ll x) const {
        return queryRec(root, L, R, x);
    }
};
struct Data {
    vector<int> ids;
    LiChao hull;
    Data(ll L, ll R, const vector<Line>* lines)
        : hull(L, R, lines) {}
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<ll> P(N);
    for (ll& x : P)
        cin >> x;
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    // Root at the unique vertex with P = 1.
    int root =
        int(min_element(P.begin(), P.end()) - P.begin());
    // Iterative traversal.
    vector<int> parent(N, -1);
    vector<int> order;
    order.reserve(N);
    parent[root] = -2;
    order.push_back(root);
    for (int i = 0; i < (int)order.size(); ++i) {
        int v = order[i];
        for (int u : graph[v]) {
            if (parent[u] != -1)
                continue;
            parent[u] = v;
            order.push_back(u);
        }
    }
    // Subtree sizes.
    vector<int> sz(N, 1);
    for (int i = N - 1; i > 0; --i) {
        int v = order[i];
        sz[parent[v]] += sz[v];
    }
    // H[v] = sum_{x outside T_v} P[LCA(v,x)].
    vector<ll> H(N, 0);
    for (int i = 1; i < N; ++i) {
        int v = order[i];
        int p = parent[v];
        H[v] =
            H[p]
            + 1LL * (sz[p] - sz[v]) * P[p];
    }
    // Score before deleting any edge.
    ll original =
        P[root] * 1LL * N * (N - 1) / 2;
    for (int v = 0; v < N; ++v) {
        if (v == root)
            continue;
        original +=
            (P[v] - P[parent[v]])
            * 1LL * sz[v] * (sz[v] - 1) / 2;
    }
    /*
        For every non-root v:
            X_v = sz[v]
            Y_v = sz[v] * H[v]
        line:
            f_v(q) = Y_v - X_v q
    */
    vector<Line> lines(N);
    for (int v = 0; v < N; ++v) {
        if (v == root)
            continue;
        lines[v] = {
            -1LL * sz[v],
            1LL * sz[v] * H[v]
        };
    }
    // Every query is in [0, N^2 + 1].
    const ll Q = 1LL * N * N + 1;
    /*
        data[v] is the merged structure for T_v.
        We process vertices bottom-up, so no recursive DFS
        is needed.
    */
    vector<unique_ptr<Data>> data(N);
    ll bestLoss = INF;
    for (int oi = N - 1; oi >= 0; --oi) {
        int v = order[oi];
        vector<int> children;
        for (int u : graph[v]) {
            if (parent[u] == v)
                children.push_back(u);
        }
        // Choose the largest child structure.
        int big = -1;
        for (int u : children) {
            if (big == -1 ||
                data[u]->ids.size() > data[big]->ids.size()) {
                big = u;
            }
        }
        unique_ptr<Data> cur;
        if (big == -1) {
            cur = make_unique<Data>(
                0, Q, &lines);
        } else {
            cur = move(data[big]);
        }
        for (int u : children) {
            if (u == big)
                continue;
            auto& small = data[u];
            /*
                a is in the smaller child-subtree and the
                other cut is in the already merged structure.
                Their LCA is v.
                loss =
                    Y_a + Y_b
                    - P_v X_a X_b.
                Therefore query b's line at
                    q = P_v X_a.
            */
            for (int a : small->ids) {
                ll q =
                    P[v] * 1LL * sz[a];
                ll partner =
                    cur->hull.query(q);
                bestLoss =
                    min(bestLoss,
                        1LL * sz[a] * H[a]
                        + partner);
            }
            // Merge the smaller structure into the larger one.
            for (int id : small->ids) {
                cur->hull.add(id);
                cur->ids.push_back(id);
            }
            small.reset();
        }
        /*
            Pair the edge above v with a descendant edge.
            loss =
                Y_v + Y_b - H_v X_b.
            Query at q = H_v.
        */
        if (v != root && !cur->ids.empty()) {
            ll partner =
                cur->hull.query(H[v]);
            bestLoss =
                min(bestLoss,
                    1LL * sz[v] * H[v]
                    + partner);
        }
        // Make the edge above v available to ancestors.
        if (v != root) {
            cur->hull.add(v);
            cur->ids.push_back(v);
        }
        data[v] = move(cur);
    }
    cout << original - bestLoss << '\n';
    return 0;
}