module graph_mod
    implicit none
    type node
        integer(4),allocatable:: to(:)
        integer(4):: l
    end type
    
contains
    subroutine init(n)
        type(node):: n
        allocate(n%to(1))

        n%l = 0
    end subroutine


    subroutine regist(n,m)
        type(node):: n
        integer(4):: m

        if (n%l+1 > size(n%to)) call add_(n)
        n%l=n%l+1
        n%to(n%l) = m
    end subroutine


    subroutine add_(n)
        type(node):: n
        integer(4),allocatable:: tmp(:)
        integer(4):: l

        l = size(n%to)
        allocate(tmp(l))
        tmp(:) = n%to(:)
        deallocate(n%to)
        allocate(n%to(l*2))
        n%to(1:l) = tmp(:)
        deallocate(tmp)
    end subroutine
end module



module deque_mod
    implicit none
    type deque
        integer(4),pointer:: v(:)
        integer(4):: l,r
        integer(4):: lmax, rmax
    end type
    private
    public:: deque
    public:: init_deque
    public:: append, appendleft
    public:: pop, popleft
    public:: right, left
    public:: remaining_elements
    public:: remain

contains
    subroutine init_deque(dq)
        ! 初期化
        type(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end subroutine


    subroutine append(dq,num)
        ! 右端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%r+1 > dq%rmax) call add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine appendleft(dq,num)
        ! 左端に挿入
        type(deque):: dq
        integer(4):: num
        if (dq%l-1 < dq%lmax) call add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine add_(dq)
        ! arrayの延長
        type(deque):: dq
        integer(4):: l
        integer(4),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(2*dq%lmax:2*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 2*dq%lmax
        dq%rmax = 2*dq%rmax
    end subroutine


    function pop(dq) result(ret)
        ! 右端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function popleft(dq) result(ret)
        ! 左端から取り出し
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function right(dq) result(ret)
        ! 右端を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%r)
    end function

    function left(dq) result(ret)
        ! 左端を確認
        type(deque):: dq
        integer(4):: ret
        ret = dq%v(dq%l)
    end function

    function remaining_elements(dq) result(ret)
        ! 残りの要素数
        type(deque):: dq
        integer(4):: ret 
        ret = dq%r - dq%l + 1
    end function

    function remain(dq) result(ret)
        ! 要素が残っているかどうか
        type(deque):: dq
        logical:: ret
        ret = remaining_elements(dq) > 0
    end function
end module


program Ki
    use graph_mod
    use deque_mod
    implicit none
    integer(4):: n,q,a,b,p,x
    integer(4):: i,t,dst
    integer(4),allocatable:: cnt(:)
    logical,allocatable:: see(:)
    type(node),allocatable:: tree(:)
    type(deque):: order, todo

    ! input -------------------------------
    read*, n,q
    allocate(tree(n), see(n), cnt(n))
    
    do i=1,n
        call init(tree(i))
    end do

    do i=1,n-1
        read*, a,b
        call regist(tree(a),b)
        call regist(tree(b),a)
    end do
    cnt(:) = 0

    do i=1,q
        read*, p,x
        cnt(p) = cnt(p) + x
    end do

    ! shori -------------------------------

    call init_deque(order)
    call init_deque(todo)

    call append(todo,1)
    see(:) = .false.

    do while(remain(todo))
        t = popleft(todo)
        see(t) = .true.
        call append(order,t)

        do i=1,tree(t)%l
            if(see(tree(t)%to(i))) cycle
            call append(todo,tree(t)%to(i))
        end do
    end do

    see(:) = .false.
    do while(remain(order))
        t = popleft(order)
        see(t) = .true.
        do i=1,tree(t)%l
            dst = tree(t)%to(i)
            if (see(dst)) cycle
            cnt(dst) = cnt(dst) + cnt(t)
        end do
    end do

    print*, cnt(:)
end program Ki

Measured memory_bytes: 31044