参考：https://www.cnblogs.com/ydtz/p/16276327.html

K-father问题（预处理复杂度-查询复杂度）

倍增，如在线求lca的fa数组即可。O(nlogn)-O(logn)
长链剖分：预处理2i级祖先，预处理长链向上向下的d个节点。跳到x的log(k)/log(2)级祖先（即对k求log2向下取整），然后跳到长链顶，然后查表长链顶往上往下d个节点，在其中找所需要的，d为所在长链长度。O(nlogn)-O(1)
栈，离线做法，dfs维护遍历过的节点。O(n)-O(1)
重链剖分+dfs序 O(n)-O(logn)

K-son问题（只求个数，不求具体哪个点）

线段树合并

考虑利用权值线段树维护深度，表示以当前节点为根的子树内每一个深度的节点个数，然后套用线段树合并的板子，从下到上依次合并即可。
没太看懂，自己的想法：
1.离线询问。
2.每一个节点开一个线段树，维护每一个深度的节点个数。然后在某个节点合并完了，查这个节点的所有询问。
但是这个法子不需要维护任何的区间信息，线段树感觉纯浪费。

树上差分

没理解为什么作者写树上差分，不过作者也说不一定算树上差分，反正是差分(。
1.离线询问
2.准备一个数组，维护当前每个深度上有多少个点。然后dfs整个树。
3.在dfs进入节点u时，记录询问深度有多少个点，此时这些点都不是u的子树的。
4.在dfs完子树，回到u，并且要返回时，记录询问深度有多少个点，此时对比之前记录的，多出来的点数都是u子树的。
应该是这个意思。

dsu on tree

不会dsu on tree

DFS 序 + 树状数组

每个子树都对应 DFS 序列中的连续一段（一段区间）
考虑将原树转为一个 dfs序，子树区间就是$[dfn_i,dfn_i+siz_i]$，那么查询就是一个二维数点问题，即查询在一个区间内，一个值的个数。需要反应过来这就是一个经典的树状数组问题。

长链剖分 + dp

长链剖分优化dp例题