Minimum Cost Security Guard Placement

During the upcoming holiday season, an underground supermarket wants to maintain order by hiring temporary security guards to monitor its corridors. The corridors form a tree structure (i.e. a connected acyclic graph) where each corridor corresponds to an edge and the endpoints of corridors are the tree's vertices. Each vertex has an associated cost for placing a security guard.

A guard stationed at one endpoint of a corridor can monitor both endpoints of that corridor. In other words, if an edge connects vertices u and v, placing a guard at either u or v will cover that edge.

Your task is to choose a set of vertices to place guards such that every edge of the tree is covered (i.e. for every edge, at least one of its endpoints has a guard) and the total cost is minimized.

The problem can be formulated as finding a minimum vertex cover on a tree. The standard dynamic programming approach uses the following recurrences in \( \LaTeX \):

[ \begin{aligned} dp[u][0] &= cost[u] + \sum_{v \in children(u)} \min(dp[v][0], dp[v][1]) \ dp[u][1] &= \sum_{v \in children(u)} dp[v][0] \end{aligned} ]

Here, \(dp[u][0]\) is the minimum cost in the subtree rooted at \(u\) when a guard is placed at \(u\) and \(dp[u][1]\) is the minimum cost when no guard is placed at \(u\). The answer is \( \min(dp[\text{root}][0], dp[\text{root}][1]) \).

inputFormat

The input begins with an integer \(n\) (\(2 \leq n \leq 10^5\)), which is the number of vertices in the tree. The next line contains \(n\) space-separated integers, where the \(i\)-th integer represents the cost of placing a guard at vertex \(i\). Then follow \(n-1\) lines, each containing two space-separated integers \(u\) and \(v\) (\(1 \leq u,v \leq n\)), representing an undirected edge (corridor) connecting vertices \(u\) and \(v\>.

outputFormat

Output a single integer, the minimum total cost required to place the guards so that every corridor is monitored.

sample

2
1 2
1 2

1