! fenwic treeでバグらない要注意

module vector_int32_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    private
    type,public:: vector_int32
        integer(int32),allocatable:: array(:)
        integer(int32),private:: l=0
    contains
        procedure:: push_back=>vec_push_back, insert=>vec_insert
        procedure:: pop_back=>vec_pop_back, pop=>vec_pop, erase => vec_erase
        procedure:: at=>vec_at, back=>vec_back, head=>vec_head
        procedure:: size=>vec_size, to_array=>vec_to_array
    end type
contains
    pure function vec_size(vec) result(ret)
        class(vector_int32),intent(in):: vec
        integer(int32):: ret

        ret = vec%l
    end function


    pure subroutine check_array_allocation(vec)
        type(vector_int32),intent(inout):: vec

        if (.not. allocated(vec%array)) allocate(vec%array(1))
    end subroutine


    function vec_at(vec,i) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32):: i,ret

        call check_array_allocation(vec)
        ret = vec%array(i)
    end function


    function vec_back(vec) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32):: ret
        
        ret = vec%at(vec%l)
    end function


    function vec_head(vec) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32):: ret
        
        ret = vec%at(1)
    end function


    pure subroutine vec_append_array(vec,l,r)
        type(vector_int32),intent(inout):: vec
        integer(int32),intent(in):: l,r
        integer(int32),allocatable:: tmp(:)
        
        allocate(tmp(l:2*r))
        tmp(l:r) = vec%array(l:r)
        call move_alloc(tmp, vec%array)
    end subroutine


    pure subroutine vec_reduce_array(vec,l,r)
        type(vector_int32),intent(inout):: vec
        integer(int32),intent(in):: l,r
        integer(int32),allocatable:: tmp(:)
        
        allocate(tmp(l:r/2))
        tmp(l:r/2) = vec%array(l:r/2)
        call move_alloc(tmp, vec%array)
    end subroutine


    pure subroutine check_allocation_size(vec)
        type(vector_int32),intent(inout):: vec
        integer(int32):: len_alloc

        call check_array_allocation(vec)
        len_alloc = size(vec%array)
        if (vec%l >= len_alloc) then
            call vec_append_array(vec,1,len_alloc)
        else if (vec%l <= len_alloc/2) then
            call vec_reduce_array(vec,1,len_alloc)
        end if
    end subroutine


    pure subroutine vec_push_back(vec, v)
        class(vector_int32),intent(inout):: vec
        integer(int32),intent(in):: v

        vec%l=vec%l+1
        call check_allocation_size(vec)
        vec%array(vec%l) = v
    end subroutine


    pure subroutine vec_insert(vec,i,v)
        class(vector_int32),intent(inout):: vec
        integer(int32),intent(in)::i, v

        vec%l=vec%l+1
        call check_allocation_size(vec)
        vec%array(i+1:vec%l+1) = vec%array(i:vec%l)
        vec%array(i) = v
    end subroutine


    function vec_pop_back(vec) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32):: ret

        ret = vec%back()
        vec%l=vec%l-1
        call check_allocation_size(vec)
    end function


    function vec_pop(vec,i) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32),intent(in):: i
        integer(int32):: ret

        ret = vec%at(i)
        vec%l=vec%l-1
        vec%array(i:vec%l) = vec%array(i+1:vec%l+1)
        call check_allocation_size(vec)
    end function


    subroutine vec_erase(vec,i)
        class(vector_int32):: vec
        integer(int32),intent(in):: i
        integer(int32):: dmp

        dmp = vec%pop(i)
    end subroutine


    function vec_to_array(vec) result(ret)
        class(vector_int32),intent(inout):: vec
        integer(int32):: ret(1:vec%l)

        call check_array_allocation(vec)
        ret = vec%array(1:vec%l)
    end function
end module


module merge_sort_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    private
    public:: merge_sort

    interface merge_sort
        module procedure ms32, ms64
    end interface
contains
    recursive subroutine ms32(ar)
        integer(int32),intent(inout):: ar(:)
        integer(int32):: m

        if (size(ar) <= 1) then
            return
        else
            m = size(ar)/2
            call ms32(ar(:m)); call ms32(ar(m+1:))
            call sub_ms32(ar)
        end if
    end subroutine


    subroutine sub_ms32(ar)
        integer(int32),intent(inout):: ar(:)
        integer(int32):: tmp(1:size(ar))
        integer(int32):: m,l,r,i
        
        tmp(:) = ar(:)
        m = size(ar)/2; l=1;r=m+1
        do i=1,size(ar)
            if (m < l) then
                ar(i:)=tmp(r:); return 
            else if (size(ar) < r) then
                ar(i:)=tmp(l:m); return
            else
                if (tmp(l) <= tmp(r)) then
                    ar(i) = tmp(l); l=l+1
                else
                    ar(i) = tmp(r); r=r+1
                end if
            end if
        end do
    end subroutine


    recursive subroutine ms64(ar)
        integer(int64),intent(inout):: ar(:)
        integer(int32):: m

        if (size(ar) <= 1) then
            return
        else
            m = size(ar)/2
            call ms64(ar(:m)); call ms64(ar(m+1:))
            call sub_ms64(ar)
        end if
    end subroutine


    subroutine sub_ms64(ar)
        integer(int64),intent(inout):: ar(:)
        integer(int64):: tmp(1:size(ar))
        integer(int32):: m,l,r,i
        
        tmp(:) = ar(:)
        m = size(ar)/2; l=1;r=m+1
        do i=1,size(ar)
            if (m < l) then
                ar(i:)=tmp(r:); return
            else if (size(ar) < r) then
                ar(i:)=tmp(l:r); return
            else
                if (tmp(l) <= tmp(r)) then
                    ar(i) = tmp(l); l=l+1
                else
                    ar(i) = tmp(r); r=r+1
                end if
            end if
        end do
    end subroutine
end module


! ar1のソート順序でar2もソートする。
module double_merge_sort_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    private
    public:: double_merge_sort

    interface double_merge_sort
        module procedure dms32, dms64
    end interface
contains
    recursive subroutine dms32(ar1, ar2)
        integer(int32),intent(inout):: ar1(:), ar2(:)
        integer(int32):: m

        if (size(ar1) <= 1) then
            return
        else
            m = size(ar1)/2
            call dms32(ar1(:m), ar2(:m))
            call dms32(ar1(m+1:), ar2(m+1:))
            call sub_ms32(ar1,ar2)
        end if
    end subroutine


    subroutine sub_ms32(ar1, ar2)
        integer(int32),intent(inout):: ar1(:), ar2(:)
        integer(int32):: tmp1(1:size(ar1)), tmp2(1:size(ar2))
        integer(int32):: m,l,r,i

        m=size(ar1)/2; l=1; r=m+1
        tmp1(:)=ar1(:); tmp2(:)=ar2(:)

        do i=1,size(ar1)
            if (m < l) then
                ar1(i:) = tmp1(r:)
                ar2(i:) = tmp2(r:)
                return
            else if (size(ar1) < r) then
                ar1(i:) = tmp1(l:m)
                ar2(i:) = tmp2(l:m)
                return
            else
                if (tmp1(l) <= tmp1(r)) then
                    ar1(i) = tmp1(l)
                    ar2(i) = tmp2(l)
                    l=l+1
                else
                    ar1(i) = tmp1(r)
                    ar2(i) = tmp2(r)
                    r=r+1
                end if
            end if
        end do
    end subroutine


    recursive subroutine dms64(ar1, ar2)
        integer(int64),intent(inout):: ar1(:), ar2(:)
        integer(int32):: m

        if (size(ar1) <= 1) then
            return
        else
            m = size(ar1)/2
            call dms64(ar1(:m), ar2(:m))
            call dms64(ar1(m+1:), ar2(m+1:))
            call sub_ms64(ar1,ar2)
        end if
    end subroutine


    subroutine sub_ms64(ar1, ar2)
        integer(int64),intent(inout):: ar1(:), ar2(:)
        integer(int64):: tmp1(1:size(ar1)), tmp2(1:size(ar2))
        integer(int32):: m,l,r,i

        m=size(ar1)/2; l=1; r=m+1
        tmp1(:)=ar1(:); tmp2(:)=ar2(:)

        do i=1,size(ar1)
            if (m < l) then
                ar1(i:) = tmp1(r:)
                ar2(i:) = tmp2(r:)
                return
            else if (size(ar1) < r) then
                ar1(i:) = tmp1(l:m)
                ar2(i:) = tmp2(l:m)
                return
            else
                if (tmp1(l) <= tmp1(r)) then
                    ar1(i) = tmp1(l)
                    ar2(i) = tmp2(l)
                    l=l+1
                else
                    ar1(i) = tmp1(r)
                    ar2(i) = tmp2(r)
                    r=r+1
                end if
            end if
        end do
    end subroutine
end module


program main
    use,intrinsic :: iso_fortran_env
    use vector_int32_mod
    use merge_sort_mod
    use double_merge_sort_mod
    implicit none
    integer(int32):: n,a,b,i
    integer(int32), allocatable:: c(:), ne(:), d(:), leaf(:), ind(:), ans(:)
    type(vector_int32),allocatable:: g(:)

    read*, n
    allocate(ne(n),source=0)
    allocate(d(n),source=n+100)
    allocate(g(n))

    do i=1,n-1
        read*, a,b
        call g(a)%push_back(b)
        call g(b)%push_back(a)
        ne(a)=ne(a)+1
        ne(b)=ne(b)+1
    end do

    allocate(c(n))
    read*, c(:)
    call merge_sort(c)
    
    allocate(ind, source=[(i,i=1,n)])
    allocate(leaf, source=pack(ind,ne==1))
    do i=1,size(leaf)
        d(leaf(i)) = 0
        call dfs(leaf(i))
    end do

    call double_merge_sort(d, ind)

    allocate(ans(n))
    do i=1,n
        ans(ind(i))=c(i)
    end do
    print'(i0)', sum(c(1:size(c)-1))
    print'(*(i0,1x))', ans(:)
contains
    recursive subroutine dfs(ind)
        integer(int32):: ind,i,t

        do i=1,g(ind)%size()
            ! print'(*(i0,1x))', d(:)
            t = g(ind)%at(i)
            if (d(t) <= d(ind)+1) cycle
            d(t)=d(ind)+1
            call dfs(t)
        end do
    end subroutine
end program main