We are given a tree of N nodes (with integer labels 1 to N). For each node in the tree, count the number of connected subgraphs in which that node has the maximum value label.

It is not too difficult to find a quadratic time solution by rerooting the tree N times and then performing an O(N) DFS with a dynamic programming step. Is it possible to solve this problem in O(N), O(N log N), or some sub-quadratic-time-complexity though?