Description

给一颗树，带边权，树根是 (S)。

每次可以给一条边权(+1) 并花费 (1) 的代价，求最小代价使得 (S) 到所有叶子距离相等。

Solution

首先(S)到所有叶子的距离一定是(max\_dep)。然后我们肯定尽量把深度浅的边权(+1)。

这时我们设(dp[x])为使(x)到以(x)为根的子树中所有的叶子距离相等的最小代价，(mx[x])表示以(x)为根的子树中深度最大的叶子节点的深度。那么有

[dp[x]=sum{dp[y]+mx[x]-mx[y](yin{sonx})} ]

（(dp)策略就是先让(x)的所有子树（以(y)为根）的叶子到(y)的距离相等，再把(x)到(y)的边贪心加，使这时(x)到它的所有叶子距离相等）

最后答案就是(dp[S])。答案记得要开(long long)！