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,2},} {4,3,1} {4,2} {4,3} {4}, 4 is the maximum node in these paths, so the answer for node 4 is 56.↵
↵
I want to know is there any $O(n)$ or $O(NlogN)$ solutions and how to solve it.↵
↵
Thank you all!
↵
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
↵
I want to know is there any $O(n)$ or $O(NlogN)$ solutions and how to solve it.↵
↵
Thank you all!
