Need help for a tree problem

Revision en2, by UltramanDecker, 2022-08-04 13:26:00

Given a tree with $$$N$$$ nodes. The tree nodes are numbered from $$$1$$$ to $$$N$$$.

For each node $$$i$$$, please print how many paths that $$$i$$$ is the maximum node in this path.

For example in a tree

For node 4, in paths {2,4,3} {2,4,3,1} {4,3,1} {4,2} {4,3} {4}, 4 is the maximum node in these paths, so the answer for node 4 is 6.

I want to know is there any $$$O(n)$$$ or $$$O(NlogN)$$$ solutions and how to solve it.

Thank you all!

Tags tree, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English UltramanDecker 2022-08-04 13:26:00 16
en1 English UltramanDecker 2022-08-04 12:25:58 525 Initial revision (published)