每日练习：P11562 寄存器

wxccd2z · 2025-01-13 21:59:25 · 个人记录

推我的团队：养老团队 (每日练习题单在里面)

一道树上连通块问题，很显然又是一个 trick 题目！同时对于我们在赛场上遇到没见过的 trick 的思考方法有所启发。

首先，我们很容易发现操作的本质是选择一个连通块，并将其反转。连通块操作问题 trick，可以直接缩成点，因为本质缩成点后的点操作可以等价于连通块操作。

这时候树变成了一层黑色一层白色的树，随后开始贪心的构造最优方法。我们发现我们在确定一个节点为根以后，答案就是树的高度，所以很显然，最优的根便是根节点，答案是 \left \lceil \frac{len}{2} \right \rceil，其中 len 是直径。

而我们思考问题的时候应该多去想想部分分，为什么会有这些特殊性质，例如这道题目的 sub3。