Solution 1

Observe that for any given node, there is a certain interval of skills that will always reach it. Initially, node ~1~ has an interval of ~[1, 10^9]~. We will use the following process to calculate the rest of the intervals:

We perform a DFS down the tree. When a node is reached, we will sort its outgoing edges by difficulty level. Then we make the following observation: if there are two hills with difficulty ~x~ and ~y~ such that ~x < y~, a skier with a skill of ~s~ will traverse down the more difficult hill if and only if ~s > \frac{x+y}{2}~. We use this property to calculate the intervals of the children of our current node (or you can skip this observation and use binary search).

Once all intervals are calculated, sort all the skills of the skiers. Then, use binary search to calculate the number of skiers who will visit each node.

Time Complexity: ~\mathcal{O}(N \log N)~

Solution 2

We make the same observation: for any given node, if there are two hills connecting to it with difficulty ~x~ and ~y~ such that ~x < y~, a skier with a skill of ~s~ will traverse down the more difficult hill if and only if ~s > \frac{x+y}{2}~. Using this property, we can maintain the path that a skier will take from the root to a leaf by processing the skiers in increasing order of skill and maintaining a priority queue for the edges. Details are left as an exercise to the reader.

Time Complexity: ~\mathcal{O}(N \log N)~