Minimum Gesture Operations

You are given a tree with n nodes. Each node i has an associated non‐negative integer weight \(a_i\). In one operation, you can choose any simple path on the tree (a simple path is a path that does not repeat vertices) and subtract \(1\) from the weight of every node on that path. Your task is to determine the minimum number of operations required so that all node weights become exactly \(0\).

Formal Statement

You are given a tree with n nodes and node weights \(a_1, a_2, \dots, a_n\). In one operation, you can select any simple path in the tree and subtract \(1\) from every node’s weight that lies on that path. Compute the minimum number of operations needed to reduce all weights to \(0\>.

Observation

One key observation is that any operation affects a connected set of nodes along a path. It can be shown that if we root the tree arbitrarily (say at node \(1\)), the answer is given by:

[ \text{Answer} = a_1 + \sum_{v \neq 1} \max(0, a_v - a_{p(v)}) ]

where \(p(v)\) denotes the parent of node \(v\) in the rooted tree. This formula works because when an operation covers both a parent and its child, it can simultaneously reduce the weight of both nodes. Any extra weight at a child node (beyond the weight of its parent) must be decreased by additional operations targeting that child.

inputFormat

The first line contains a single integer n (\(1 \le n \le 2 \times 10^5\)) — the number of nodes in the tree.

The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)), where \(a_i\) is the weight of the \(i\)th node.

Each of the next n-1 lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\)) indicating that there is an undirected edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer, the minimum number of operations required to reduce all node weights to exactly \(0\).

sample

2
3 5
1 2

5