树相关小结

树上一些比较经典或是可能比较偏其实是自己太菜没学过不太会的内容

孩子兄弟表示法

把普通的树转化为二叉树

实现

对于一个点，如果它在原树中有儿子，则随便找一个（或按某种顺序选取）在二叉树中把它做为它的左儿子；如果在原树中有兄弟，那么随便找一个（或按某种顺序选取）在二叉树中作为它的右儿子，不断递归构造（即左孩子右兄弟）

应用

一般不需要真正建出来，在表达式树/某些树形dp中用到了这个思想

prufer序列

常用于有标号的无根树计数

• 无根树转prufer序列

  每次选取编号最小的叶子，把它父亲记录，并把它自己删除

• prufer序列转无根树

  设点集$V={1,2,3,...,n}$，每次取出prufer序列中最前面的元素$u$，在$V$中找到编号最小的没有在prufer序列中出现的元素$v$，给$u$，$v$连边然后分别删除，不断重复此过程。最后在$V$中剩下两个节点，给它们连边。最终得到的就是无根树。

结论/应用

• 任何一棵无根树都有一种prufer序列与它一一对应，反之亦然
• 有编号无根树计数：$n^{n-2}$
• 有编号有根树计数：$n^{n-2}*n = n^{n-1}$
• 可以均匀地随机一棵树
• prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1
• $n$个节点的度为$deg[i]$的无根树共有$\frac{(n-2)!}{\sum_{i=1}^{n}(deg[i] - 1)!}$个，因为此时prufer编码中的数字$i$恰好出现次

长链剖分

一种$O(n)$合并深度相关信息的方法：见此

这里介绍另外一种形式，用来$O(n\log n)-O(1)$求$k$祖先

首先不难发现一个性质：

任意一个点的$k$级祖先所在链的链长一定大于等于$k$

因为如果这个点和他的$k$级祖先在一条链上，那么结论显然成立。

如果不在一条链上，那么一开始这个祖先没有选择这棵子树是因为别的子树更深，故而所在链一定是大于$k$的，结论仍然成立。

对于每条重链，在每条重链顶部预处理出重链顶端向上$k$步之内的祖先，以及向下$k$步重链上的所有点。$k$为重链长度。再对每个点求出$2^i$祖先的倍增数组

考虑询问$x$的$k$级祖先，先利用倍增数组跳$2^l$祖先，其中$l$满足$\frac{k}{2}<l\le k$（即$k$的最高位），设剩余层数为$k'$，可以发现$k'< \frac{k}{2}$

利用之前证明的性质，我们可以发现当前节点所在链链长一定严格大于$k'$

如果链头在当前节点的$k'$级祖先上面，那么我们利用链头向下的数组可以得到答案，否则利用向上的数组得到答案

可以发现询问总复杂度是$O(1)$的