度娘的定义
Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2。
对于一棵确定的无根树,对应着唯一确定的prufer序列
如下图的prufer序列为\(3,5,1,3\)
例如,对于prufer序列\(3,5,1,3\) 连边顺序为 \(2,3\), \(5,4\), \(1,5\), \(3,1\), \(3,6\) (实际上与构建prufer序列时相同) 以上两种操作都可以用set维护,时间复杂度\(O(nlogn)\)
暂且写这些吧,先做做题,然后继续整理