?https://codeforces.com/problemset/problem/101/D

題意：

給一棵 (n) 個節(jié)點的帶權樹，求一種遍歷方案，從 節(jié)點(1) 出發(fā)，每條邊走兩次，走過所有點，第一次經(jīng)過每個節(jié)點的平均時刻最小。輸出這個平均時刻。

題解：

樹形DP + 概率 + 排序,?

szt[v]? 遍歷子樹v的每個頂點再返回, 即子樹v的所有邊時間的2倍(包含父親u到v)。

?res[u] 不是遍歷 樹u 的每個頂點時間總和，而是遍歷 樹u 的每個頂點時刻之和。

?找出一個dfs遍歷方案，使得 res[1]最小。

?最后答案是 res[1]/(n-1), 即遍歷 樹u 的每個頂點時刻之數(shù)學期望。