Need help for a tree problem

Правка en2, от 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!

Теги tree, data structures

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский UltramanDecker 2022-08-04 13:26:00 16
en1 Английский UltramanDecker 2022-08-04 12:25:58 525 Initial revision (published)