2024/02/19(#19)：孤独被染上童话底色

今天尝试能不能效率正常一点！！

类似于 Conquer The World，直接每次反悔贪心遍历整棵树有 48 分。所以为啥去年不会啊。

删除的话套一层线段树分治就可以了，现在想一想怎么加入。

考虑模拟反悔贪心，找到 $x$ 的祖先中深度最深的满足 $s(u)=\operatorname{siz}_u$ 的 $u$ ，然后替换子树内的最小值。

树剖线段树维护每个节点的 $\operatorname{siz_u}-\ s(u)$ 的最小值以及子树内的最小权值，直接替换即可。

sjy 能不能做个人啊，把树剖卡满的意义何在啊。代码。

今天打了一下月赛 Div.2！非常搞笑！

以后可以尝试把 E 补了！F 是什么牛马题！

并查集暴力模拟即可，注意询问离线来减小常数。

考虑暴力， $f_{x,y}$ 是否存在 $x\rightarrow y$ 的回文路径，直接记忆化搜索 $O(n^2 + m^2)$ 。

问题是我们的边数太多了！注意到路径长度其是不太要紧，因为可以来回走刷分。首先考虑一个事情，如果我只能走同色点，那么我们好像不能改变我们当前刷的路径长度的奇偶性——除非有奇环。除非……除非不是二分图！

那么对于二分图的同色连通块，可以只保留一棵生成树（因为子图也是二分图），其它同色连通块可以表示为一棵生成树，然后有一个自环。

而异色点是自然二分图，直接保留生成树即可。代码。

唉，大意了😅

不要让欲望侵占了意志。