Max Nodes on Upward Path

Problem Statement

Max Nodes on Upward Path Problem Description You are given a rooted tree with N nodes (root is node 1). Each node i contains A[i] candies. For any starting node u , you may collect candies from u then climb to its parent, then to the parent's parent, and so on — collecting all candies of every visited node. You must stop as soon as collecting the next ancestor would make the total candies exceed K . (You may also stop earlier, but optimal play always takes as many as possible.) Find the maximum number of nodes you can collect (consecutive nodes on an upward path, starting from some node and repeatedly going to parent) such that the total candies collected is ≤ K . Input Format: First line: two integers N and K . Second line: N integers A[1] A[2] ... A[N] . Next N-1 lines: two integers u v meaning an undirected edge between nodes u and v . The tree is rooted at node 1. Output Format: Single integer: maximum number of nodes collectible on any upward path whose sum of A values is ≤ K . Ex