今天啥也没干。
早上他妈的为什么傻逼学校还让我们跑操啊???，妈的出一身臭汗然后去机房睡都难睡着。但是昨天晚上写了树分块发现无处存储确实就是树分块板子，于是今天早上跑操的时候发了呆想了会细节。
上午就把那个傻逼无处存储给写了?，想着就是个板子，写起来跟吃屎一样难受。想了半天没想到个空间 \(n+O(\sqrt n)\) 的 lca 求法，就去看了看题解???，最后索性直接开赫！
下午看了看数据结构，jimmy 让讲 noip2021 和 2020 的题?，摆了！
晚上去 P 站找图，是谁没找到几张好看的啊，是谁啊是谁啊???
恋恋长得像洛天依/yiw
Tibrella 10:36:12 crimson000 你头像好像洛天依Tibrella 10:37:38
确实像吧
Tibrella 10:37:44
绿眼睛
Tibrella 10:37:58
然后那块我也不知道叫眼影还是叫啥的
Tibrella 10:38:01
地方是红的
头像原图：
被haosen说之前的图不好看了/kk
crimson000 发了一些 arc 周年贺图
haosen 10:41:31
哇哦
haosen 10:41:47
王队近来的图图越来越好康了
/kk 我之前发的图难道不好看吗/kk
戴老师的经验之谈（确信）
贪得无厌的haosen?
haosen 21:20:05
crimson000 鲜花呢
crimson000 21:20:35
正在写
haosen 21:20:44
彳亍
haosen 21:20:48
要图图
crimson000 21:20:57
？
crimson000 21:20:58
你不发
crimson000 21:21:01
我就不发（
我现在才会用 html 这个玩意是不是有点晚了（
推歌：666 -RoughSketch
我他妈就是要推音游曲！
一个字：爽！敲起来真的很爽，无法用语言来形容的爽，能听到高潮那种。
P8353
好好好把毒瘤题写了。
也算裸的树分块板子吧，把路径拆成散块和整块，关键点之间直接按照分块的思路打标记，散点直接暴力加。
但是这题最傻逼的就是空间限制不允许再开一个 \(n\) 的数组，所以撒关键点只能随机撒，并且 lca 还贼你妈难求。
随机撒点，并且向上标记建出来虚树，同时记录虚树上每个点走哪个儿子第一个到达的关键点，记为 \(nxt[u][son]\)。
几个关键函数，实现完了就基本做完了：
dep(u)：获得 \(u\) 的深度，直接预处理出每个关键点的深度，查询的时候直接暴力跳到关键点。
bottom(u)：得到 \(u\) 往下走遇到的第一个关键点。我们先暴力向上跳到关键点，然后用我们预处理的 \(nxt\) 查询即可。
lca(u, v)：不用多说了。我们先两个点都暴力向上跳到第一个关键点，如果第一个关键点相等，就直接朴素 lca 即可。否则就求出这两个关键点的 lca，一定就是我们要求的两个点的 lca。
这三个函数搞完基本就做完了，\(O(\sqrt n)\) 数组随便开，空间复杂度 \(O(2n+\frac{n}{w}+O(\sqrt n))\)。
haosen 不发图我就不放图了???
还是放一张吧，之前翻谢拉 P 站的作品翻到的，才知道谢拉一开始是画车万的
