10.31 闲话

迟到的闲话。

本来应该当晚更新，但因为当晚跟别人一起 emo 去了，没更。

有题解。

每日抽象

tankard 还是非常乐的，在今天的 tankard 对决中，真神诞生了，他叫 Hugoi。

“我将对我的队友重拳出击！！！”

---

中午出去吃饭，发现高三生在校外都是成双成对的，我吃饭那桌对面就坐了一对儿，俩人在聊周边，立牌抱枕啥的，但也不说是啥的周边，不知道是饭圈的还是二次元的。

但是我吃不好饭了。

在机房发现就连蚊子都成对儿出现，不过叮人的蚊子好像都是雌的，所以这算不算女同？

一起飞过来那就一起去死吧！

放图：

BA 好图还是不少的，可惜我找图那个网站啥也没有，我也不敢在机房上蓝 P。

只有一张了 /kk。

看来以后找图还是得回家找。

口呼梯阶

CF938E NN country

倍增 + lca + 树状数组

首先需要处理出从某个点向上跳 \(2^i\) 步能到达的最浅的点

加入一条路径时可以给其两端标记为 lca，更新的时候标记由子向父更新，能处理出跳一步到达的最浅点，之后倍增即可。

对于询问，将两点倍增向上跳，不到达 lca，首先特判几种情况：一，其中某个点到达不了 lca，无解；二，其中某个点本身就是 lca，答案是另一个点跳的步数 \(+1\)。

对于一般情况，我们需要判断跳完以后这两点之间有无直接路径，若有，答案为步数 \(+1\)，否则为 \(+2\)。

注意到两点间若有直接路径，其两端点一定分别在两点对应的子树内，而子树满足 dfs 序连续，所以可以在 dfs 序上树状数组维护。具体地，将询问和所有路径离线，路径分为起点终点，询问分为左右端点，按询问左端点 dfs 序排序并依次插入，遇到询问更新其左端前前的所有路径，在树状数组上路径终点的位置更新，对于询问，在其左端点 \(dfn-1\) 处和 \(dfn+siz-1\) 处分别查询其右端点子树 dfs 序区间内的终点个数，作差可以得到有多少起终点分别在询问左右端点对应的子树内的路径。

P2633 Count on a tree

可持久化线段树

首先将路径问题转化为两点到根的问题，发现需要维护的东西是一个前缀，需要支持查询两前缀之间第 \(k\) 小的树，可以使用可持久化线段树。具体地，dfs 过程中建树，子结点在父结点基础上更新，求答案时类似树上差分，子节点相加减 lca 再减去 lca 的父亲，此处减不是直接减去，而是指可持久化线段树查询时的作差操作。