因为是春天到来时写的题，所以就叫春日纪行啦。
但是这首歌我有点想不起来调子的说。
会省选前陆陆续续地更完的
P5284 [十二省联考 2019] 字符串问题
首先，我们考虑暴力建图。
我们考虑对所有的 \(A\) 类串连向自己的 \(B\) 类串。然后所有的 \(B\) 类串都连向别的 \(A\) 类串满足是他的前缀。然后令所有 \(A\) 类串的点权是 \(1\)，\(B\) 类串的点权是 \(0\)。
这样如果出环了就是 \(-1\)。然后跑一边拓扑就行。
然后我们考虑优化这个建图。
我们能想到建一棵后缀树。后缀树有一个性质就是树上一个节点表示的字符串一定是所有子树表示的子串的前缀。这样我们让所有给出的子串都找到对应节点，然后让 \(A\) 类点挂在树上，\(B\) 类点挂在连向所在节点，这就相当于让 \(B\) 连向所有合法的 \(A\) 了。
找到子串对应的节点是容易的。就在 \(SAM\) 上记录一下最后位置，然后倍增向上跳到合法位置即可。
我们发现这样做是不对的。因为同一个节点上所有点没有区别，所以不能判断 \(B\) 是否能向所有这个节点的点连边。我们需要对这个点内部进行拆点。我们对同一节点上所有子串按长度排序，同一长度 \(A\) 在后面。然后倒序枚举。如果现在是 \(A\) 类串，那么直接由虚点连到自己就行，如果是 \(B\) 类点，那么直接由自己连向虚点，并且新建一个虚点，连向原来的虚点。这样就能保证同一节点内的是正确的。
然后就没了。但是写了一晚上加一下午。代码能力缺乏是这样的。
[IOI2018] werewolf 狼人
我认为做这道题是需要一首 bgm 的。
IA 小天使真可爱
我们考虑从两头开始随便走，如果能走到的点是存在交集的，就说明是能走到的。现在考虑怎么求。
我们复习 Kruskal 重构树。
Kruskal 重构树有一个重要的性质。\(x\) 和 \(y\) 的 \(lca\) 的点权就是 \(x\) 到 \(y\) 的所有简单路径的最大边权的最小值。
那么我们按照最小值为边权建一棵按边权从大到小的重构树，再建一棵以较大值为边权的按边权从小到大的重构树。这样我们从起点开始，不停地跳父亲，跳到最高的点使得点权大于等于 \(L\)。对于终点也是这样跳。这样跳到的位置的子树内所有点都是从起点或终点能直接走到的位置。我们考虑怎样对这两部分求交。
我们发现每个点都有两个 dfn 值，每次找到的都对应一段 dfn 的范围。也就是对于每个询问都有两个范围，求都满足的个数。这显然是个二维偏序。