題目連結:http://www.51nod.com/Contest/Problem.html#contestProblemId=3957
\(n\)個點的一棵樹，第\(i\)個節點上的動物有\(\frac{a_i}{100}\)的機率加入，每個加入的動物都會每秒向父節點移動。
對于第\(i\)隻動物，如果它到達一個節點時還沒有其他動物比他早來過，那麼它的權值加一。
現在對于每一隻動物求它參加的話它的期望權值。
\(1\leq n\leq 10^5,1\leq a_i\leq 100\)
考慮一個動物\(x\)能拿到一個節點\(y\)的權值的條件，也就是\(y\)的子樹中深度比\(x\)小的動物都不參賽的機率。
也就是對于一個動物\(x\)，動物\(z\)能對它産生影響首先要求\(dep_z<dep_x\)，并且隻會從\(LCA(x,z)\)處向上開始産生影響。
發現一個特點是從\(LCA\)處産生影響，這就和[LNOI2014]LCA很像了，我們對于會産生影響的\(z\)把它到根節點上的路徑都修改了，然後直接詢問\(x\)到根節點路徑上的權值就好了。
至于\(dep_z<dep_x\)這個條件我們把所有節點按照深度從小到大排序然後處理即可。
時間複雜度：\(O(n\log^2 n)\)