从 这里 看到的.
假设我们有一棵 \(n\) 个点的树 (边权都为 \(1\)), 我们随便选取一个点 \(r\) 作为根.
记 \(d_u\) 为点 \(u\) 的度数, \(\text{dis}(u,v)\) 为 \(u\) 到 \(v\) 的距离, \(T(u)\) 为点 \(u\) 的子树.
则我们有结论:
\[n-1=\sum\limits_{u}(2-d_u)\text{dis}(u,r) \]证明考虑数学归纳法. 显然原式对于孤立点成立. 对于我们要证明的树 \(T(x)\), 假设对于以 \(x\) 的所有儿子 \(u_1,u_2,\cdots,u_k\) 为根的子树 \(T(u_i)\) 都有上式成立.
于是我们只需证明:
\[\sum\limits_{i=1}^k\sum_{v\in T(u_i)}(2-d_v)\text{dis}(v,r)=k+\sum\limits_{i=1}^k(3-d_u)+\sum\limits_{i=1}^k\sum_{v\in T(u_i),v\neq u_i}(2-d_v)(\text{dis}(v,r)-1) \]经过一系列计算得到只需证:
\[\sum\limits_{u}(2-d_u)=2 \]然后因为 \(\sum\limits_{u}d_u=2(n-1)\), 上式显然.
如果从容斥的方面考虑也是很容易理解的.
标签：结论,子树,limits,text,sum,为点,关于,有趣,dis From： https://www.cnblogs.com/pjykk/p/16814688.html