树的重心 by江河湖海

引入

重心是什么？

想象你有一个由线悬挂的秋千，秋千的两端坐着两个人，如果这两个人坐在秋千的重心上，秋千就会保持平衡。在树的结构中，重心就是那个让所有节点到它那里的“距离”（可以理解为线的长度）总和最小的点。

重心为什么最多只有两个？

假设树的重心有两个，我们称它们为A和B。如果A和B不是相邻的，那么在它们之间会有一条路径，这条路径上的节点到A和B的距离总和就不可能最小，因为我们可以找到一个点在A和B之间的路径上，使得总距离更小。所以，如果有两个重心，它们必须是相邻的。

重心为什么相邻？

继续用秋千的例子，如果A和B不是相邻的，你可以想象它们是秋千的两端，而中间的路径就像是连接两端的秋千座椅。如果A和B之间有一个点C，那么C到A和B的距离总和肯定比A或B到它们自己的距离总和要小，因为C更接近秋千的中间。这就违反了A和B是重心的条件。

如何找到重心？

想象你在玩一个游戏，你要把所有的点（可以想象成是树上的苹果）都拉到一个点上，使得拉线总长度最短。你开始时可能随便选一个点，然后你发现，如果你把这个点稍微移动一下，总长度就会变短。你继续移动，直到你发现无论怎么移动，总长度都不会再变短了，那么这个点就是重心。

重心如何移动？

如果你在树上加一个苹果（增加一个节点），重心可能会移动，但最多只移动到相