[NFLS 1437/6] 圣诞老人 题解

大意

给定一棵树，对于任意的三个点 a,b,ca, b, c , 求 dˉ,d=dis(a,b)+dis(b,c)+dis(c,a)\bar d, d = dis(a, b) + dis(b, c) + dis(c, a) .

解法

对于每条边，计算对于答案的贡献.

设 left(x),right(x)left(x), right(x) 为该边左右的点数.

left(x)⋅right(x)⋅(left(x)−1)+left(x)⋅right(x)⋅(right(x)−1)n(n−1)(n−2)6=6(left(x)right(x))n(n−1)\frac {left(x) \cdot right(x) \cdot (left(x) - 1) + left(x) \cdot right(x) \cdot (right(x) - 1)} {\frac {n(n - 1)(n - 2)} 6} = \frac {6(left(x)right(x))} {n(n-1)}