module mod_vector
    implicit none
    private

    type :: vector
        integer :: N
        integer, allocatable :: array(:) 
    end type vector

    public :: vector
    public :: make, append, vecsize, arr

  
contains

subroutine make(vec)
    implicit none
    type(vector) :: vec
    allocate(vec%array(10))
    vec%N = 0
    return
end subroutine make

function vecsize(vec) result(ret)
    implicit none
    type(vector) :: vec
    integer :: ret
    ret = vec%N
    return
end function vecsize

subroutine append(vec, x)
    implicit none
    type(vector) :: vec
    integer, allocatable :: tmp(:)
    integer :: x
    integer :: N

    N = vec%N
    if(N < size(vec%array)) then
        vec%array(N + 1) = x
        vec%N = N + 1
    else
        allocate(tmp(N))
        tmp = vec%array
        deallocate(vec%array)
        allocate(vec%array(2*N))
        vec%array(1:N) = tmp
        vec%array(N + 1) = x
        vec%N = N + 1
    end if
    return
end subroutine append

function arr(vec, i) result(ret)
    implicit none
    type(vector) :: vec
    integer :: i, ret
    ret = vec%array(i)
    return
end function arr

end module mod_vector


program prob5
    use mod_vector
    implicit none
    type(vector), allocatable :: G(:)
    integer :: N
    integer :: a, b, i
    integer, allocatable :: ans(:), c(:), queue(:)
    integer :: ind, v, last, su, s
    logical, allocatable :: used(:)
    read(*,*) N

    allocate(G(N), c(N), ans(N), used(N), queue(N))

    do i = 1, N
        call make(G(i))
    end do
    do i = 1, N-1
        read(*,*) a, b
        call append(G(a), b)
        call append(G(b), a)
    end do
    read(*,*) c
    call msort(c)

    ind = 1
    last = 2
    do i = 1, N
        used(i) = .false.
    end do
    queue(1) = 1
    used(1) = .true.
    
    do while(last <= N)
        v = queue(ind)
        s = vecsize(G(v))
        do i = 1, s
            if(.not. used(arr(G(v), i))) then
                queue(last) = arr(G(v), i)
                used(arr(G(v), i)) = .true.
                last = last + 1
            end if            
        end do
        ind = ind + 1
    end do

    do i = 1, N
        ans(queue(i)) = c(N - i + 1)
    end do
    su = 0
    do i = 1, N-1
        su = su + c(i)
    end do

    write(*,*) su
    write(*,*) ans




    stop
contains


  !
  ! swap two arguments
  !
subroutine swap(a, b)
    implicit none
    integer, intent(inout) :: a, b

    integer :: c

    c = a
    a = b
    b = c

  end subroutine swap

  !
  ! merge sort
  !
  recursive subroutine msort(x)
    implicit none
    integer, intent(inout) :: x(:)

    integer :: n, mid, i, j, k
    integer, allocatable :: tmp(:)
    
    n = size(x)
    
    if(n == 1) then
      return
    end if

    !
    ! 前半と後半に分けてソート
    ! 1~midとmid+1~nをそれぞれソート済みにする
    !
    mid = n / 2
    call msort(x(:mid))
    call msort(x(mid+1:))

    !
    ! tmpという配列にxを一時的に保管
    ! マージソートは外部ソート
    !
    allocate(tmp(n))
    tmp = x

    ! tmpの後半部分を左右反転
    do k = n, mid+1, -1
      tmp(k) = x(mid + n - k + 1)
    end do

    ! iは前半のリストのうちまだ見ていないものの最小値
    ! jは後半のリストのうちまだ見ていないものの最小値
    ! kは見た回数の合計
    i = 1
    j = n

    do k = 1, n
      !
      ! 一番左と一番右のうち小さい方をxに入れていく
      ! ここが等号つき不等号なので、安定ソートとなる
      !
      if(tmp(i) <= tmp(j)) then
        x(k) = tmp(i)
        i = i + 1
      else
        x(k) = tmp(j)
        j = j - 1
      end if
    end do
    
    deallocate(tmp)
    return
  end subroutine msort

end program prob5

Measured memory_bytes: 4356