目录

1. 曼哈顿距离与切比雪夫距离的相互转化
2. prufer序列

---

1. 曼哈顿距离 与 切比雪夫距离 的相互转化

曼哈顿距离

|x1−x2|+|y1−y2|=max(x1−x2+y1−y2,x1−x2−y1+y2,−x1+x2+y1−y2,−x1+x2−y1+y2)$|x_1-x_2|+|y_1-y_2|=max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2)$
与某一个点的曼哈顿距离均为d的所有点构成了一个以该点为中心的对角线长度为2d的菱形。

切比雪夫距离

max(|x1−x2|,|y1−y2|)=max(x1−x2,x1+x2,y1−y2,y1+y2)$max(|x_1-x_2|,|y_1-y_2|)=max(x_1-x_2,x_1+x_2,y_1-y_2,y_1+y_2)$
与某一个点的切比雪夫距离均为d的所有点构成了一个以该点为中心的边长为2d的正方形。

两种距离之间的转化

由于两种等距离的形状均为正方形，因此可以通过旋转坐标系来互相转化。

(1)曼哈顿距离->切比雪夫距离

将所有的点做变换(x,y)$(x,y)$->(x+y,x−y)$(x+y,x-y)$。

证明

令x3=x1+y1,y3=x1−y1,x4=x2+y2,y4=x2−y2$x_3=x_1+y_1,y_3=x_1-y_1,x_4=x_2+y_2,y_4=x_2-y_2$
|x1−x2|+|y1−y2|=max(x1−x2+y1−y2,x1−x2−y1+y2,−x1+x2+y1−y2,−x1+x2−y1+y2)=max(x3−x4,y3−y4,−y3+y4,−x3+x4)=max(|x3−x4|,|y3−y4|)$|x_1-x_2|+|y_1-y_2|=max(x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y_2,-x_1+x_2-y_1+y_2)=max(x_3-x_4,y_3-y_4,-y_3+y_4,-x_3+x_4)=max(|x_3-x_4|,|y_3-y_4|)$

(2)切比雪夫距离->曼哈顿距离

将所有的点做变换(x,y)$(x,y)$->(x+y2,x−y2)$(\frac{x+y}{2},\frac{x-y}{2})$。

证明

令x3=x1+y12,y3=x1−y12,x4=x2+y22,y4=x2−y22$x_3=\frac{x_1+y_1}{2},y_3=\frac{x_1-y_1}{2},x_4=\frac{x_2+y_2}{2},y_4=\frac{x_2-y_2}{2}$
max(|x1−x2|,|y1−y2|)=max(x1−x2,−x1+x2,y1−y2,−y1+y2)=max(x3+y3−x4−y4,−x3−y3+x4+y4,y3−x3+y4−x4,−y3+x3−y4+x4)=|x3−x4|+|y3−y4|$max(|x_1-x_2|,|y_1-y_2|)=max(x_1-x_2,-x_1+x_2,y_1-y_2,-y_1+y_2)=max(x_3+y_3-x_4-y_4,-x_3-y_3+x_4+y_4,y_3-x_3+y_4-x_4,-y_3+x_3-y_4+x_4)=|x_3-x_4|+|y_3-y_4|$

---

2.prufer序列

定义

prufer序列是一颗带编号的无根树的编码表示方式，一颗具有n$n$个节点的带编号的无根树有唯一的长为n−2$n-2$ 的prufer序列。

因为每种带编号的无根树对应唯一的prufer序列，所以prufer序列也被用作无根树的计数。

–如下图的无根树的prufer序列为–

3,5,1,3$3,5,1,3$

1.如何从一个无根树得到prufer序列？

找树的编号最小的叶子节点，然后将与叶子节点相连的节点编号加入到prufer序列中去，然后删掉这个叶子节点。重复上述过程直到树上只剩2个节点为止，即得到长为n−2$n-2$的prufer序列。

显然prufer序列是唯一的。

2.如何从prufer序列恢复一颗无根树？

找到prufer序列中未出现过的，编号最小的点，这个点即为最远一次被删除掉的，把这个点与prufer序列中的第一个点相连，并弹出prufer中的这个点，重复上述操作，prufer序列处理完成后，剩余两个点直接连到一起即可。

3.重要性质

1. prufer序列中每个编号出现的次数+1等于该编号的点在无根树中的度数。

2. n$n$个点的无向完全图计数为n(n−2)$n^{(n-2)}$

3. n$n$个点，每个点的度数为D1,D2,...,Dn$D_1,D_2,...,D_n$，则prufer序列的种数为(n−2)!(D1−1)!(D2−1)!...(Dn−1)!$\frac{(n-2)!}{(D_1-1)!(D_2-1)!...(D_n-1)!}$

例题

n$n$个点中，其中有m$m$个点的度数是未知的，求生成树的种数？

记remain$remain$为剩余出现次数
remain=(n−2)−(Di1−1)−(Di2−1)−...−(Din−m−1)$remain=(n-2)-(D_{i1}-1)-(D_{i2}-1)-...-(D_{in-m}-1)$

先把m$m$个点看成是一种点。
这样答案就是(n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!$\frac{(n-2)!}{(D_{i1}-1)!(D_{i2}-1)!...(D_{in-m}-1)!remain!}$
而实际上剩余次数remain$remain$里面的点可以随意填，形成各种不同的排列，即答案要乘以mremain$m^{remain}$

因此最终的答案就是：
(n−2)!(Di1−1)!(Di2−1)!...(Din−m−1)!remain!mremain$\frac{(n-2)!}{(D_{i1}-1)!(D_{i2}-1)!...(D_{in-m}-1)!remain!}{m}^{remain}$

其他计数类型

1.有标号有根树的计数

nn−2∗n=nn−1$n^{n-2}\ast n=n^{n-1}$

2.无标号无根树的计数

3.无标号有根树的计数

---