首先定义无根树中度数为1的节点是叶子节点。找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下2个节点。这个序列为这棵树的Prufer序列。一棵有\(n\)个节点的无根树的Prufer序列的长度为n-2。显然，一棵无根树可以一一对应一个Prufer序列。而

\(purfer\)序列，是为了证明\(cayley\)定理。具体来说，是将一个树映射到一个数组上，在数组上可以使得很多东西更加清晰的展示。构造\(prufer\)序列\(prufer\)是将一个大小为\(n\)的树映射到长度\(n-2\)的序列上。从一个无根树开始，我们将树入度为\(1\)的点找出来，及叶子

定理：对于一个有\(n\)个节点的无根树，它的结构可以有\(n^{n-2}\)种可能。至于证明，我们可以用\(prufer\)序列来证明。\(prufer\)序列度娘给出的定义是：\(Prufer\)数列是无根树的一种数列。在组合数学中,\(Prufer\)数列由有一个对于顶点标过号的树转化来的数列，点数为n的树

Prufer序列Prufer序列可以将一个带标号 n 个节点的树用 [1,n]中的 n−2 个整数表示，即 n 个点的完全图的生成树与长度为 n−2 值域为 [1,n] 的数列构成的双射。Cayley定理节点个数为n的无根标号树的个数为nn-2扩展Cayley定理1n个标号节点形成一个有s颗树的

CH定理主要用于优化线性递推。下面很多东西都是自己瞎琢磨的，大概错漏挺多。线代的一些基本知识感觉学习CH困难的很大一部分原因就是缺少一些线代的基础。矩阵的秩\(r(A)<n\)，说明向量组线性相关，说明行列式\(|A|=0\)。反之，如果\(|A|\neq0\)，那么矩阵满秩。即二者充要。

传送门解题思路关于Prufer序列的构造，见OI-wiki这里直接放结论：一个Prufer序列与一个无根树一一对应度数为\(d_i\)的节点在序列中出现了\(d_i-1\)次\(\sum(d_i-1)=n-2\)n个点的完全图的生成树有\(n^{n-2}\)种所以相当于n-2个数（有重复的）进行全排列，答案即为：\[\frac

A已知一个字符串\(n\le1e3\)中的若干信息，：\((x,y,z)\)表示\(x\)后缀和\(y\)后缀的\(\text{LCP}=z\).求满足条件的字典序最小的字符串。已知\(a_{x+i}=a_{y+i}(i<z)\)，考虑维护并查集，一定相同的在一个集合。然后要处理的是\(a_{x+z}\neqa_{y+z}\)。从前往后填即可。

一.写在前面p.s学习自https://www.cnblogs.com/dirge/p/5503289.html二.prefur序列1.由无根树生成prefur序列首先定义无根树中度数为1的节点是叶子节点。找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下2个节点。2.由prefur序列生成无根树设点集

目录前言Hello！小伙伴！非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ 自我介绍ଘ(੭ˊᵕˋ)੭昵称：海轰标签：程序猿｜C++选手｜学生简介：因C语言结识编程，随后转入计算机专业，有幸拿过一些国奖、省奖…已保研。目前正在学习C++/Linux/Python学习经验：扎实基础+多做笔记+