关于迟到

这么多天就迟到一次就被抓了个正着/jk

今天刚好错过地铁，后来在地铁上碰见了 int08，本来他和我都坐的上一班结果今天都迟到了，然后在路上就一直讨论李老和 hfu 抓住我们的概率。本来我想今天迟到就算了，毕竟刚好错过地铁下一班要等好一会没办法，但 int08 认为他有很大概率被抓，所以我们尽量走快点。万万不幸，刚好七高东北大马路的超长红绿灯在我们走到时刚好变红（恼，最后到了 int08 的机房时同时撞见李老和 hfu，好一个欧亨利式的结尾！

dsu on tree

今天是一位从前没见过（也有小概率可能见过忘了）的学长给我们讲 \(\text{dsu on tree}\) 和线段树合并。以前的知识我基本忘了，约等于零基础。最开始学长给我们讲了树上启发式合并的核心，就是根据子树大小或深度去选择重儿子，暴力跑轻儿子。这种算法（或者叫思想）用于解决树上问题（离线可处理动态），以维护子树信息为主，主要包含 \(\text{add}\) 操作。将树拍成区间维护。

线段树合并的话，我的理解是在树上维护信息时可以对于每个点都动态开点线段树维护信息，然后递归合并答案。写起来就是线段树多了一个合并（merge）操作，在此不赘述。

对于这两个算法，学长找了许多较为“简单”的题目。感觉有一部分是经典的维护信息的题目，还有一部分是先推性质然后就可做的题，最后一类就是在树上 DP 然后考虑优化。因为我对于这两类算法不熟悉，所以上午没有怎么切题。总结为太菜了。

上午最后在学长的注视下写一道很简单的数论题结果有一个小问题交了九发才过，尴尬。

下午就一直写 dsu，感觉终于理解了，并且深有体会，不知道是不是悟透了。

晚上因为有朋友请客在外面吃饭，回家时有些晚，没力气干事了，所以开颓。颓了一个小时才开始写随笔。