长链剖分查K级祖先
在WC上第一次听到这个次，但他们表示这个只是预备只是就不讲了。。。
我学了这么多年OI怎么没听过呢？百度也搜不到啊！！！
然后今天突然乱翻遇到这个算法。。。在wiki上有详细的英文版，没有中文版。。。那就翻译一下吧
https://en.wikipedia.org/wiki/Level_ancestor_problem
算法作用：O(nlogn)预处理，O(1)回答第k级祖先。
首先预处理出倍增数组
然后按照深度剖分，然后把每条链向上延长自己的长度的一倍。于是如果一个点的子树深度为d，那么他可以O(1)查询自己的前d级祖先。
所以每次查询先倍增跳一次，然后长链剖分跳一下就到了。
然后据说用四毛子算法可以做到O(n)-O(1)。
预处理所有大小小于(logn)/4的子树