Hero's Journey in a Tree

Problem Statement

Hero's Journey in a Tree Problem Description You are given a tree with n nodes numbered 1 to n , rooted at node 1 , and n - 1 edges. Every edge holds a monster with power p . A hero lands on a node u with initial health H and climbs toward the root, one edge at a time, always moving from his current node to its parent. Before crossing an edge he must battle the monster on that edge. With current health H and monster power p : If H < p , the hero cannot win and stops at his current node. If H > p , the hero defeats the monster, loses p health, and moves to the parent node. If H = p , the hero defeats the monster, loses all his health ( H becomes 0 ), ascends to the parent node, but dies on arrival. A hero who dies on arrival still counts as having reached that parent node, and he goes no further. (inferred - the source says he "ascends to the parent node"; since every monster has power at least 1, a hero with 0 health cannot win another battle.) For each query, determine the highe