【学习笔记】树的直径，重心

草莓 Strawberry

• 膜拜 EternalAlexander
• 假设$|S|\ge 2$，设直径的两个端点为$s$和$t$
• 显然我们知道直径有一个中心
• 假如我起点不在半径上，那么我下一步会把所有在半径上的点占领
• 但是显然我可以把起点调整到半径上，然后把所有半径上的点占领
• 然后我们对于其他的点求出到半径上的点的最大距离，排序过后就可以得到$S\times G$的的最大值

CF1387B2

• 对于一条边$(u,v)$，每条边对答案贡献最多为$2\min (siz[u],n-siz[u])$
• 考虑找到重心，对除了重心外的点两两跨子树匹配
• 因为任意子树大小不超过$\frac{n}{2}$，所以存在两两配对的方案
• 细节问题就不说了

树的直径

• 给定一棵树，求编号$[l,r]$内两点距离的最大值。$n\le 10^5$
• 考虑树上两个点集$S$和$T$，若集合$S$中的最远点对是$u\to v$，$T$中的最远点对是$w\to x$，那么$S\cup T$的最远点对一定是$u\to v$，$w\to x$，$u\to w$，$u\to x$，$v\to w$，$v\to x$ 六对之一
• 可以线段树维护。可以用欧拉序列求$LCA$平衡复杂度做到预处理$O(n\log n)$，询问$O(1)$。
• 总复杂度$O(n\log n)$。

哈夫曼树(Hufman Tree)

• 构造方法：每次取权值最小的两个点，加一个新的节点作为他们的父节点，将新的节点权值设为它们的前缀和。