P1099
直接把直径揪出来从一边到一边扫过去就行了。
【记录】
P5659
按照字典序贪心，对每个点维护相邻的边的删除顺序， 实际上细节并不多。
【记录】
P5666
考虑计算每个点作为重心的次数。
首先把随便一个重心拿出来做根， 然后显然 x 要想作为重心就不能切 x 子树里的边。（这一步真 tm 妙
）
那么剩下的情况就是切边后，
- x 和原来的根不在一个连通块里
- x 和原来的根在一个连通块里
如图。
以下用 (siz_x) 表示以 x 为根的子树的节点个数。
对于切断的边 (e)， 称上面的那个点为 (up_e)， 下面的那个点为 (down_e)。
设 (g_x = maxlimits_{yin son(x)}{siz_y})。
使用的重心判断方法是去掉其后任意连通块的大小乘 2 后都不超过整棵树的大小。
那么对于情况 1， 如果 x 为重心， 那么
- (2 imes g_xle siz_{down_e})
- (2 imes (siz_{down_e}-siz_x)le siz_{down_e})， 即 (2 imes siz_xge siz_{down_e})
对于情况 2， 如果 x 为重心， 那么
- (2 imes g_x le siz_{rt}-siz_{down_e})
- (2 imes(siz_{rt}-siz_{down_e}-siz_x)le siz_{rt}-siz_{down_e})， 即 (2 imes siz_xge siz_{rt}-siz_{down_e})
特别地， 对于根，设其最大子树的根为 u， 次大子树的根为 v， 若删去的边不是 u 里面的也没有把 u 割出去， 那么需要满足 (2 imes siz_ule siz_{rt}-siz_{down_e})； 若使 (siz_u) 变化了或直接没有了， 显然 u 这个子树是满足条件的， 那么剩下的就是要判断剩下的子树， 即 (2 imes siz_vle siz_{rt}-siz_{down_e})。
可以发现都是值域上区间查询的形式， 不过要差分出正确的数据结构。
具体地， 对于情况 1， dfs 时维护到根的树状数组即可；对于情况 2， 维护全局的树状数组， dfs 时维护到根的树状数组， 利用树上差分差分出子树的树状数组。
挺简单的， 代码也不难写。
【记录】