Gold
Batch
Editorial available
Orchard Arbitration
/orchard-arbitration
Version
v1
Published
Apr 23, 2026, 10:56 PM
Updated
Apr 23, 2026, 10:56 PM
Testsets
1
Statement
Rendered as plain statement text from the published version.
# Orchard Arbitration
## Problem
Farmer Bessie has a collection of orchards arranged in a tree structure. Each orchard can produce milk with a certain value. However, there's a constraint: if two adjacent orchards are both selected, they will interfere with each other and both become worthless.
Your task is to select a subset of orchards such that no two selected orchards are adjacent in the tree, and the total value is maximized.
## Input
The first line contains an integer $N$ ($1 \leq N \leq 100,000$), the number of orchards.
The second line contains $N$ space-separated integers $v_1, v_2, \ldots, v_N$ ($1 \leq v_i \leq 10,000$), where $v_i$ is the value of orchard $i$.
The next $N-1$ lines describe the tree structure. Each line contains two integers $u$ and $v$ ($1 \leq u, v \leq N$, $u \neq v$), indicating that orchards $u$ and $v$ are adjacent.
## Output
Print a single integer: the maximum total value Bessie can obtain by selecting orchards such that no two selected orchards are adjacent.
## Constraints
- $1 \leq N \leq 100,000$
- $1 \leq v_i \leq 10,000$
- The input forms a valid tree
## Sample
### Input
```
5
4 2 7 1 3
1 2
1 3
3 4
3 5
```
### Output
```
9
```
### Explanation
The tree has 5 orchards with values [4, 2, 7, 1, 3]. Orchard 1 is adjacent to orchards 2 and 3. Orchard 3 is adjacent to orchards 1, 4, and 5.
The optimal selection is orchards 2 and 3, yielding a total value of 2 + 7 = 9. We cannot do better because if we include orchard 1 (value 4), we exclude orchards 2 and 3, which have a combined value of 9. Alternatively, selecting orchards 1, 4, and 5 gives 4 + 1 + 3 = 8, which is less than 9.