A. 追逐游戏 (chase)
没啥意义的水题，但赛时没调出来。
分讨，LCA
设 \(S\) 和 \(T\) 的 LCA 为 \(lca\)
-
\(S'\) 为 \(lca\) 的祖先节点的时候，\(S'\) 到达 \(s->T\) 这条链上的第一个点 \(x\) 一定是 \(lca\)
-
否则，用 LCA 求出来 \(S'\) 到 \(s->T\) 这条链上的第一个点 \(x\)（\(x\) 要么是 S 与 S' 的 LCA，要么是 T 与 S' 的 LCA）
判断 \(S'\) 到 \(x\) 的时候 \(S\) 有没有到 \(x\)，到了则答案一定是两个人都到 \(T\) 点的时候；否则答案就是 \(S->S'\) 路径上 两人一起走，最早的相遇位置
B.统计
hash
举个例子，如以下形式时，\([i,j]\) 区间显然时合法区间
发现我们只需要维护多出来的红色部分的 hash 值，并用 map 记录每种 hash 值出现的次数即可
需要卡常，各种 map 好像很难过，需要手写哈希表，直接粘的板子，改天仔细学习一下
C.软件工程
贪心、思维、前缀最大值优化 dp
分为两种情况做
-
直接贪心，考虑把最长的 \(k-1\) 条线段各放一个集合，其余的放到一个集合里
-
处理一下 dp
线段大致分为以下几种形式：
对于 1 线段这种存在一条线段（2 线段）被自己完全覆盖的，容易发现它若和 2 线段放一起，那么贡献就是 2 号线段的贡献。
所以我们考虑去掉 1 线段这一类的线段，这样我们把剩余的线段按左端点排好序后，也能保证右端点是单调不减的，那么显然同一个集合里我们选连续的一些线段是较优的
这样 dp 就是显然的了，转移如下：
前缀最大值优化一下就好啦
最后记得把去掉的那些有包含线段的线段的贡献加到答案上，具体就是对于表示选了 \(j\) 个集合的 \(f_{j}\) 加上 去掉的那些线段里前 \(k-j\) 大的长度总和 更新答案