UltramanDecker's blog

By UltramanDecker, history, 2 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it