題目連結：http://codeforces.com/problemset/problem/280/C
推薦閱讀部落格：http://blog.csdn.net/qq574857122/article/details/41688045
題意：給定一個有根樹，然後對這個樹進行操作，删除某個節點i及其所有的後代節點，已經删除了的節點不能再次删除，然後不斷這樣操作，直到把所有的節點全部删除了位置，
然後題目要求一個數學期望，考慮把所有的節點全部都删除掉需要多少步，每次選擇删除的節點是随機的（當然不能選擇已經删除掉了的節點），删除操作步數的數學期望，
思路：直接考慮感覺比較麻煩，如果直接考慮所有的情況，肯定是不行的，會逾時，那麼是不是可以換個思路想，統計每個節點對答案的貢獻
直接求是設随機變量x為步數，即xi代表的是節點i出現的步數那麼E(X)=sum(Pi*xi)
也可以設随機變量y為每個節點出現在所有操作序列中次數的數學期望，E(Y)=sum(yi)
好吧前面我自己也不知道寫的是什麼，記住這個就好了，統計每個節點對答案的貢獻
首先需要把操作序列泛化，而不是直接考慮按題目意思來構造操作序列
記一個1,2...,n 的n元排列，那麼按照序列的次序來進行删除操作，那麼如果這個節點以及在前面的操作過程中删除了，就不算它對答案的貢獻吧，因為它不是一個有效步吧
那麼要怎麼算他對答案的貢獻了，首先要知道一個節點的祖先節點的數目，也就是節點的深度d，假設根的深度為1
在所有的n元排列中（一空有n!)種，在考慮第i個節點的時候，如果他對答案有貢獻，那麼他就要是在删除他前面的操作之前沒有被删除，也就是說前面沒有他的祖先，
等價于他的祖先全部都在删除他的操作的後面，那麼怎麼計算這個數目呢，
可以這樣考慮所有的n!的排列中，一共有d個節點是需要特别考慮的（包括節點i自己），先給出公式( n!*(d-1)!)/d!
解釋：所有的排列中如果那d個節點是固定的，那麼就有n!/d!種其他節點的不同排列，由于隻需要節點i在他的祖先的前面，那麼祖先的d-1個節點有(d-1)!中
所有總共有( n!*(d-1)!)/d!種情況下節點i是會對答案有貢獻的，他們每個節點隻會有一步的貢獻，也就是n!/d
那麼他都數學期望的貢獻就是(n!/d)/n! ,（因為有n!中情況呀）
也就是1/d ,好吧真是太簡潔了，
那麼計算題目的答案就隻需要算所有節點的深度的倒數的和就可以了，隻需要dfs（因為是樹，可以直接找到深度）或者bfs一遍就好了