Orchard Arbitration

# 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.