概述

预计 $100+100+4=204$，实际 $100+100+0=200$，和想的差不多。

赛时

拿到 pdf，看到 T1，构造，再看两眼，画个图，哦我会了。只要构造一个长度为 $2$ 的菊花，然后剩下的再连一个链出去就好了。

于是直接开始写，写了五分钟吧。。然后又花 30min 写+调 checker，哈哈。。。。。

反正把所有数据都测了一遍，没问题。。

于是看 T2，字符串题。。等会再说。

看 T3，计数，DP，看到本质不同子序列忽然想到一个叫子序列自动机的玩意。。。不可做！（大雾）

于是看 T2，退火没前途，二分没前途，高斯消元好像挺对的，但也没啥前途（没细想）。

毕竟是后缀的 lcp，能用到的东西也不怎么多。开始枚举知识点！

于是用一些后缀数据结构往上套，主要套后缀数组和后缀树。。

然后玩了好几个数据（aab，aabaa，aaba，abaa 等）。

aab 比较有启发啊，然后在后缀树上模拟了一波好像明白了。

就是设 $f_i$ 表示已经把这个子树上分好了的答案，我们对于每个点只考虑它与它父亲多出来的长度的贡献。

对于直接就是原串后缀的点，贡献就是多出来的长度；如果不是原串后缀，那么就是多出来长度加上把儿子分一下。

这个分儿子的过程，具体来说，设儿子的 $f$ 值为 $f_1,f_2,f_3\dots f_m$，然后你需要构造 $k_1,k_2,k_3\dots k_m$，使 $\sum k=1$ 且 $\max(f_ik_i)$ 最小。

然后想一想，所有 $f_ik_i$ 都相等肯定是最优的（否则可以调整成相等使更优），然后再随便推一推，$\max(f_ik_i)=\dfrac{1}{\sum_{j=1}^m\dfrac{1}{f_j}}$。

（我也讲不清楚了，可以看代码）

（其实好像不是多出来长度贡献，而是一个类似区间 DP 的思想？或者说选父亲就不选儿子？）

（实际上上述过程花了很长很长很长时间，主要是对于只考虑多出来长度这部分想了很久才勉强想清楚）

于是写完了，又发现被卡空间了，卡了一阵子，卡完之后也不剩什么时间了，急忙开 T3。。

我会 $O(nq)$ 暴力DP！

写写写，怎么过不去样例啊。。。。。

好吧好像是错的，哦好像可以改成 $O(nmq)$，也是有分的，写写写。。。

好家伙没时间了，结果没调出来。。。那就这样吧。。

赛后

T2 数据错了，题面 $n=10^6$，结果数据 $n=10^4$？？？

因为数组开小 T3 白送的 $4$ 分好像也没拿到，悲剧。。。

怎么说呢，T2 冥思苦想也不会的时候，也许应该先开 T3 打一打暴力。。。

枚举知识点实在是过于耗费时间了。。。

然后看了别人的代码和题解意识到我 T3 当时想的那个 $O(nq)$ 确实错了，但是 $O(nmq)$ 的做法是对的…总之 DP 这个东西还是要仔细想一下，硬莽好像不是很对。

总结

反正今天这个 T2 和 T3 真不好说。。

T3 其实也不是特别难，如果花时间想还是能得一些分数的，正解可能想不太到，但暴力有希望能多拿几十分。

主要是 $m\leq200$，就让人遐想…

但是这个 T2 实在是有点让人上头，主要是要用后缀数据结构有点明显了，然后就一直想往上套。。

std 的分治做法也得学一学，我现在 SA 水平真的是很差。。。