写在前面：为了保护正睿题目版权，这里不放题面，只写题解。
“我发现问题的根源是大家都不会前缀和。”——敦爷
- A
敦爷spj写错了，差点把蒟蒻swk送走
(50pts:)
考虑不输出方案怎么做。显然是树形dp。
设(f_{i,j,{0/1/2}})表示(i)的子树中，有(j)条链，根节点状态为：({)没选(/)选了向下的一条链(/)选了向下的两条链(})的最优解。
对于一棵子树，开始时只考虑根节点，依次合并每个儿子。合并时需要枚举父亲和儿子的状态，用(size)限制枚举上界，可以证明复杂度是(O(nk))的。
转移的时候分别讨论各个状态之间的转移即可。
(100pts:)
输出方案也不难，只需要记录每个状态依次从哪个儿子的哪个状态转移来即可。
可以把转移方向放在儿子上，避免复杂的可持久化。
当然写起来就是另一回事了
复杂度证明：
合并大小分别为(x,y)的两棵子树，复杂度为(O(min(x,k)cdot min(y,k)))。
不妨设(xgeq y)，对两棵子树的三种情况分别分析。
①(xgeq k, ygeq k)，则单次复杂度(O(k^2))，但这样的子树最多(frac{n}{k})棵，总复杂度(O(nk))。
②(xgeq k, y < k)，发现每个节点最多合并进(sizegeq k)的子树一次，即整棵树上每个零散节点最多产生(O(k))的复杂度，总复杂度(O(nk))。
③(x<k,y<k)，对于一个节点，最多与(O(k))个节点合并后，子树大小就会(geq k)，因此每个节点最多产生(O(k))的复杂度，总复杂度(O(nk))。
- B
(60pts:)
对于一次操作([x,y])，区间([l_i,r_i])被访问的充要条件是：([x,y])与([l_i,r_i])有交；([x,y])不完全包含([l_i,r_i])的父亲。
由此可以得到一个(O(nq))的算法，即对线段树上的每个节点分别统计访问次数。实现时有很多分类讨论，比较复杂。
(100pts:)
对于(O(nq))算法里的分类讨论，每种讨论实际上都可以提取出一个关于(x,y)的低次多项式。
发现如果区间([l_i,r_i])被([x,y])包含，则它的每一个子区间都被其包含。因此整个子树可以规避分类讨论，预处理多项式系数即可。
即询问时遇到完全包含的节点可以直接退出，复杂度等同于线段树区间询问，(O(n+qlog n))。
- C
(60pts:)
发现(h_{i+1}-h_i)等于(i)位置结束的每个子串的(G_i)之和，即([1,i])每个前缀的末尾增加了一个字符。
把(n)个后缀拉出来跑kmp，维护一下前缀和即可。
(100pts:)
对于字符串(A)，(f_i)的含义其实是(A[1…i])的border（相等的前后缀）个数。
由此得到(G_A)的含义是(A)的每个前缀出现的次数(-1)之和，因为每次枚举到这个前缀第一次出现以外的位置时，都会产生一次border的贡献。
再考虑(h_{i+1}-h_i)，即(sum_{j=1}^i G_{S[j…i]})的意义，发现对于(S[1…i])的每个子串，设其出现次数为(d)，产生的贡献为(frac{d(d-1)}2)。
用后缀自动机维护，每次加入新字符时，等价于(fail)树上到根节点的链(+1)，可以离线树剖或者LCT维护。