树相关笔记

一、树的直径

就是树上最长的一条链。

法一：两次 dfs

先随便挑一个点，dfs 找到离这个点最远的点，再从找到的这个点出发 dfs，找到离这个点最远的点，这两点之间的路径就是直径。

法二：dp

随便挑一个点往下 dp，找到从每个点 $u$ 出发往子树内走到叶子的最长链 $d_{1, u}$ 和次长链 $d_{2, u}$ ， $max {d_{1, u} + d_{2, u}}$ 就是直径。

二、树的重心

就是找到一个点，使以他作为根时，最大的子树大小，比以任何其他点作为根时的最大子树大小都要小。

直接一次 dfs 就能找到。

三、Prüfer 序列

P6086 【模板】Prufer 序列。

1. 定义

用一个长度为 $(n - 2)$ ，值域为 $[1, n]$ 的序列表示一棵树。

构建方法：每次找到编号最小的叶子节点 $u$ ，记他的父亲为 $f a$ ，将 $f a$ 加入序列并删去 $u$ 。

2. 构造

显然可以 $O (n)$ 构造，就直接从小到大遍历编号，这个编号是叶子节点就判断它父亲的编号是否比叶子节点还要小，是的话就接着删，否则继续遍历。

3. 性质

每个点在序列中出现的次数即为其度数减一。

因为每个点的所有 $c$ 个儿子都会最终成为叶子结点，将这个点加入序列 $c$ 次，而这个点的度数显然是 $c + 1$ （加上连向父亲的边）。

4. 重建树

由性质，可以从 Prüfer 序列知道每个点的度数，哪些是叶子节点。同样从小到大遍历编号，找到最小的叶子结点，将每个点父亲从前往后设为 Prüfer 序列的每个编号即可。

如果某个点被连接的次数等于他儿子的个数，那他也相当于一个“叶子结点”，往上连边。判断他的连接次数也是很好维护的。

5. 性质

一个有 $n$ 个点的完全无向图有 $n^{n - 2}$ 个生成树。

一个树对应一种 Prüfer 序列的填法，Prüfer 序列 $(n - 2)$ 个位置每个位置都有 $n$ 种填法。

6. Caylay 公式

P2290 [HNOI2004] 树的计数。

相当于规定了每个点在 Prüfer 序列中出现的次数。

为方便表述，令 $a_{i} \leftarrow d_{i} - 1$ （题目中的 $d_{i}$ ，原理即第 $3$ 点提到的性质），令 $m \leftarrow n - 2$ 。

第一个点 $m$ 个位置随便选 $a_{1}$ 个组合地放，第二个点 $m - a_{1}$ 个位置随便选 $a_{2}$ 个组合地放，以此类推：

C_{m}^{a_{1}} C_{m - a_{1}}^{a_{2}} \dots C_{m - \sum_{i = 1}^{m - 1} a_{i}}^{a_{m}}

即

\frac{m! (m - a_{1})! \dots (m - \sum_{i = 1}^{m - 1} a_{i})!}{a_{1}! (m - a_{1})! a_{2}! (m - a_{1} - a_{2})! \dots a_{m}! (m - \sum_{i = 1}^{m} a_{i})!}

红色的全都消掉了，蓝色的因为 $(\sum_{i = 1}^{m} a_{i}) = m$ ，所以值等于 $1$ 。

那么就是

\frac{m!}{\prod_{i = 1}^{m} a_{i}!}

树相关 笔记 ​

一、树的直径 ​

法一：两次 dfs ​

法二：dp ​

二、树的重心 ​

三、Prüfer 序列 ​

1. 定义 ​

2. 构造 ​

3. 性质 ​

4. 重建树 ​

5. 性质 ​

6. Caylay 公式 ​