学习笔记

树的重心

首先可以借助简单换根维护以每个点为根的，其余点到当前点的距离之和。不管是点权还是边权都可以做，复杂度 \(O(n)\)。

有一个结论是一棵树的重心一定在节点 \(1\) 所在的重链上，所以可以通过 \(O(n)\) 预处理，\(O(h)\) 求重心。

[SHOI2005] 树的双中心

显然可以枚举一条边，然后割断后求两颗树的重心。

割断后，可以用 \(O(h)\) 更新每个节点子树大小，借助预处理重儿子，次重儿子，可以 \(O(1)\) 求断边后的儿子，换根转移复杂度 \(O(nh)\)。

[CSP-S 2019] 树的重心

按照题目模拟。

考虑如何快速求一个子树内重心编号，对于节点 \(x\) 可以预处理出重链，然后倍增跳到重链上最后一个节点 \(y\) 满足 $siz_y\ge \(\left\lceil\dfrac{siz_x}{2}\right\rceil\)。\(y\) 和 \(y\) 的父亲都有可能合法，check 一下即可。

对于整棵树去掉一个子树的情况，假设割掉 \((x,y)\) 其中 \(x\) 是 \(y\) 的父亲，可以换根维护 \(x\) 为根节点的重儿子，不难 \(O(1)\) 快速做到，然后套用上面的方法即可，复杂度 \(O(Tn\log n)\)。