静态top tree，非常好数据结构!
22集训队胡策 R3 B. 举办乘凉州喵，举办乘凉州谢谢喵
大家都会静态top tree做法，就是不停split直到这条链被拆成了$\log$个cluster path，然后直接在此时的收缩树上dfs即可。
我们有一个点分治+重链剖分+长链剖分的1$\log$做法。考虑祖先-后代链咋做，大家都知道轻子树大小和是$n\log n$级别，所以就重链剖分，轻子树的部分预处理一个二维前缀和，这里离线扫链，那么每次更新的是一个前缀的前缀和，所以复杂度很对。但是跳轻边的时候需要加上重子树减去轻子树，这里可以用一个长剖解决，也就是计算子树内距离$\leq k$的点，相当于用总点数减去距离为$k+1$的点的子树大小之和。然后顶上还需要点分一下求子树外的。任意链当然是一样的。
我们可能有一个点分治+重链剖分的复杂度相同的做法，但是我不太懂。感觉在这个题上没比静态top tree好多少。127出的时候被我俩$\log$嗯草了。
cf1098 F. Ж-function
大家不都会静态top tree做法，所以我们考虑区间和区间的lcp不如后缀和后缀的lcp，相当于求$\sum\limits_{i=l}^r\min(\mathrm{lcp}(i,l),i-r+1)$，所以先建后缀树对吧。
现在你可能会了静态top tree做法，我们对$\min$讨论，$\mathrm{lcp}(i,l)\leq i-r+1$也就是$\mathrm{lcp}(i,l)-i\leq -r+1$，那么就比较的简单了，把$i$挂到$\mathrm{lca}$上，那么每次是在一个前缀上二维数点(还有编号在$[l,r]$)，然后还要特殊处理$\mathrm{lca}$是$l$的情况。
直接树剖会得到一个$\log^3$做法，但是这只是一个三维问题啊。考虑序列上的三维问题我们是咋做的，直接对一维分治即可。这里有一维是树，那么我们肯定先对树分治，毕竟静态树分治比动态树数据结构简单的程度远大于静态序列分治比动态序列数据结构简单的程度。不需要静态top tree，考虑点分治，每次处理经过分治中心的贡献，发现类似于 购票 地，这样真的砍去了树的这一维。也不需要静态lct了。
但是其实你看到这种问题当然是点分治而不是静态top tree啊?为什么我会把它放在这。