SoDumbIam's blog

By SoDumbIam, history, 5 months ago, , Can someone tell me how to solve this problem ALIENINV

Thanks! Comments (3)
 » When you ask for help with a problem, say what you already came up with (more instructions here).A good first step might be to compute the answer for every leaf. Take a leaf $L$ and root the tree there. For every other vertex $V$, it will be removed before $L$ if and only if the whole subtree of $V$ has values smaller than the value in $L$. Let $s[V]$ be the size of the subtree of $V$. Then, we want $L$ to have the smallest value among $s[V]+1$ vertices (that subtree and vertex $L$ itself), so the probability of $L$ being the smallest is $\frac{1}{s[V]+1}$. Since this is the probability of $V$ being before $L$, you can sum this up to get the expected value of the place of $L$ — because with that probability the place of $L$ is increased by $1$.This is $O(N)$ solution to find an answer for a single leaf. I don't know how hard it is to apply it for non-leaf vertices. Try it and let us know.
•  » » Thanks a lot for your help. I'll keep in mind about the instructions next time. And do you mean $L$ should have the largest value than the whole subtree of $V$? or am I missing something?Thanks!
•  » » » Yup, the largest.