module mod_t_list
  implicit none
  type :: t_list
    integer :: vol
    integer, pointer :: arr(:)
  end type t_list
  private
  public :: t_list, init_list, release_list,push_back
  public :: pop_back, get_at, size_of_list
contains
  subroutine init_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    list%vol = 0
    allocate(list%arr(1))
    return
  end subroutine init_list
  subroutine release_list(list)
    implicit none
    type(t_list), intent(inout) :: list
    if (associated(list%arr)) deallocate(list%arr)
    return
  end subroutine release_list
  subroutine push_back(list,item)
    implicit none
    type(t_list), intent(inout) :: list
    integer, intent(in) :: item
    integer, allocatable :: tmp(:)
    if (size(list%arr).eq.list%vol) then
      allocate(tmp(list%vol))
      tmp = list%arr
      deallocate(list%arr)
      allocate(list%arr(2*list%vol))
      list%arr(1:list%vol) = tmp
      deallocate(tmp)
    end if
    list%vol = list%vol+1
    list%arr(list%vol) = item
    return
  end subroutine push_back
  function pop_back(list) result(item)
    implicit none
    type(t_list), intent(inout) :: list
    integer :: item
    item = list%arr(list%vol)
    list%vol = list%vol-1
    return
  end function pop_back
  function get_at(list,i) result(item)
    implicit none
    type(t_list), intent(in) :: list
    integer, intent(in) :: i
    integer :: item
    item = list%arr(i)
    return
  end function get_at
  function size_of_list(list) result(s)
    implicit none
    type(t_list), intent(in) :: list
    integer :: s
    s = list%vol
    return
  end function size_of_list
end module mod_t_list
module mod_t_graph
  use mod_t_list
  implicit none
  integer, parameter :: infty = 1000000000
  type :: t_graph
    type(t_list), pointer :: edges(:)
  end type t_graph
  private
  public :: infty
  public :: t_graph, init_graph, release_graph, add
contains
  subroutine init_graph(graph,n)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: n
    integer :: i
    allocate(graph%edges(n))
    do i = 1, n
      call init_list(graph%edges(i))
    end do
    return
  end subroutine init_graph
  subroutine release_graph(graph)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer :: n, i
    if (.not.associated(graph%edges)) return
    n = size(graph%edges)
    do i = 1, n
      call release_list(graph%edges(i))
    end do
    deallocate(graph%edges)
    return
  end subroutine release_graph
  subroutine add(graph,x,y)
    implicit none
    type(t_graph), intent(inout) :: graph
    integer, intent(in) :: x, y
    call push_back(graph%edges(x),y)
    return
  end subroutine add
end module mod_t_graph
module mod_attack_to_a_tree
  use mod_t_list
  use mod_t_graph
  implicit none
  integer, parameter :: infty4 = 1000000000
  integer(8), parameter :: infty8 = 1000000000000000000_8
  integer :: n, dp(5000), dp1(5000), num(5000)
  integer(8) :: a(5000), dp2(5000,5000)
  logical :: ok(5000)
  type(t_graph) :: tree
contains
  subroutine solve()
    implicit none
    integer :: u, v, i
    a = 0_8
    dp = -1
    dp1 = -1
    dp2 = 0_8
    num = 0
    ok = .false.
    read(*,*) n
    read(*,*) a(1:n)
    call init_graph(tree,n)
    do i = 1, n-1
      read(*,*) u, v
      call add(tree,u,v)
      call add(tree,v,u)
    end do
    write(*,'(i0)') dfs(1,-1)-1
    return
  end subroutine solve
  recursive function dfs(v,p) result(m)
    implicit none
    integer, intent(in) :: v, p
    integer :: m, i
    m = dp(v)
    if (m.ne.-1) return
    m = dfs1(v,p)
    do i = 1, size_of(v,p)
      if (dfs2(v,i,p).lt.0_8) then
        m = min(m,i)
        exit
      end if
    end do
    dp(v) = m
    return
  end function dfs
  recursive function dfs1(v,p) result(m)
    implicit none
    integer, intent(in) :: v, p
    integer :: m, i, e
    m = dp1(v)
    if (m.ne.-1) return
    m = infty4
    if (a(v).lt.0_8) return
    m = 0
    do i = 1, size_of_list(tree%edges(v))
      e = get_at(tree%edges(v),i)
      if (e.eq.p) cycle
      m = m+min(dfs1(e,v),dfs(e,v)+1)
    end do
    dp1(v) = m
    return
  end function dfs1
  recursive function dfs2(v,e,p) result(m)
    implicit none
    integer, intent(in) :: v, e, p
    integer(8) :: m, y
    integer :: i, j, s, t, l
    m = dp2(v,e)
    if (ok(v)) return
    ok(v) = .true.
    dp2(v,:) = infty8
    dp2(v,1) = a(v)
    s = 1
    do i = 1, size_of_list(tree%edges(v))
      t = get_at(tree%edges(v),i)
      if (e.eq.p) cycle
      do j = s, 1, -1
        y = dp2(v,j)
        dp2(v,j) = y+dfs2(t,1,v)
        if (j+dfs(t,v).le.size_of(v,p)) then
          dp2(v,j+dfs(t,v)) = min(dp2(v,j+dfs(t,v)),y)
        end if
        do l = size_of(t,v), 2, -1
          dp2(v,j+l-1) = min(dp2(v,j+l-1),y+dfs2(t,l,v))
        end do
      end do
      s = s+size_of(t,v)
    end do
    m = dp2(v,e)
    return
  end function dfs2
  recursive function size_of(v,p) result(m)
    implicit none
    integer, intent(in) :: v, p
    integer :: m, i, e
    m = num(v)
    if (m.ne.0) return
    m = 1
    do i = 1, size_of_list(tree%edges(v))
      e = get_at(tree%edges(v),i)
      if (e.eq.p) cycle
      m = m+size_of(e,v)
    end do
    num(v) = m
    return
  end function size_of
end module mod_attack_to_a_tree
program attack_to_a_tree
  use mod_attack_to_a_tree
  implicit none
  call solve()
  stop
end program attack_to_a_tree